We can further optimize by reducing the number of unwanted strikes. If i and j are co-factors of number n i.e j x i = n , then there is no need to strike off multiples of i which are < i*i (square of i ) where j < i In other words the for loop for j can start at i ( when i=3 , j can start at 3 instead of 2 , because the multiples of i < (i*i) i.e for multiples of i
@@aor6956 I was going to say this for those who are wondering about the proof here goes: you might think this Gentleman has asked you to skip numbers from i*2-i*(i-1) for each i but if you observe all these numbers have already been marked of by numbers from 2 to (i-1) for which we have already marked the sieve. Therefore we can start from j = i*i and still get away with it.
I homeschool, but I knew the equation. However, I can't teach something if I can't explain it. I've been looking but none explained it so well to me. Now I can explain it to someone else. Thank you for taking your time to give a very good explanation.
Thanks a lot. Very very helpful lessons! I`ve noticed something confusing in 3:01. "If 2 is prime, then all multiples of 2 cannot be prime". Actually, any multiple of any positive integer cannot be prime, no matter if the factor is prime. Please let me know if I`m missing something.
for any grid that is a square, you only need to work out the first row of numbers. the numbers left uncrossed in the grid will be primes. so for n=1,000,000, you only need to work out the first row of 1,000 to find every prime in the 1,000x1,000 grid.
I propose much more simplier "matrix sieve" algorithm for finding prime numbers: In order to find all primes (up to a given limit) in the sequence S1(p)=6p+5,(p=0,1,2,3,...): Step 1a. Starting from 5 cross out each 5th member of the row of positive integersN(n)=0,1,2,3,4..., i.e remove the following integers: 5, 10, 15,... Step 1b. Starting from 5 cross out each 7th member of the row of positive integers, i.e remove the following integers: 5, 12, 19,.. Step 2a.Starting from 23 cross out each 11th member of the row of positive integers, i.e remove the following integers: 23, 34, 45,... Step 2b. .Starting from 23 cross out each 13th member of the row of positive integers, i.e remove the following integers 23, 36, 49,... ......... Step ia. Starting from (6i^2−1) cross out each (6i−1)th member of the row of positive integers. Step ib. Starting from (6i^2−1) cross out each (6i+1)th member of the row of positive integers. Remaining members of N(n) are indexes p of all primes (up to a given limit) in the sequence S1(p)=6p+5: p=0,1,2,3,4,...,6,7,8,9,...,11,..,13,14,....,16.....p=and primes are 5,11,17,23,29,...,41,47,53,59,...,71,...,83,89,... In order to find all (up to a given limit) primes in the sequence S2(p)=6p+7,(p=0,1,2,3,...): Step 1a. Starting from 3 cross out each 5th member of the row of positive integers, i.e remove the following integers 3,8,13,... Step 1b. .Starting from 7 cross out each 7th member of the row of positive integers, i.e remove the following integers 7,14,21,... Step 2a.Starting from 19 cross out each 11th member of the row of positive integers, i.e remove the following integers 19,30,41,... Step 2b. .Starting from 27 cross out each 13th member of the row of positive integer, i.e remove the following integers 27,40,53,... ......... Step ia.Starting from (6i^2−1−2i) cross out each (6i−1)th member of the row of positive integers. Step ib.Starting from (6i^2−1+2i) cross out each (6i+1)th member of the row of positive integers. Remaining members of N(n) are indexes p of all primes (up to a given limit) in the sequence S2(p)=6p+7: p=0,1,2,..,4,5,6,..,9,10,11,12,...,15,16.... and primes are7,13,19,...,31,37,43,...,61,67,73,79,...,97,103,... C++ program: www.planet-source-code.com/vb/scripts/BrowseCategoryOrSearchResults.asp?lngWId=3&blnAuthorSearch=TRUE&lngAuthorId=21687209&strAuthorName=Boris%20Sklyar&txtMaxNumberOfEntriesPerPage=25
I have been trying to find the most optimized method to find prime numbers. Yours was most efficient and easiest to understand so far. Upon experimenting, I found a more optimised solution. In second nested for loop where j starts from 2. we multiply j to i where i starts from 2 -> sqrt(n) Instead of using 2 we can set j = i in the second nested loop lets say i = 5 and j = 2 as of now but since 5 * 2 = 10, 5 * 3 = 15 , 5 * 4 = 20 where 10, 15, 20 are already covered by 2 and 3 respectively. there is no need to override those 0 from Prime[] array. we could directly go to 5 * 5 where 25 isnt marked yet 0. What can be the time complexity of this new approach? #include #include using namespace std; int main() { cout.sync_with_stdio(false); unsigned long int n = 100000; unsigned long int i,j; int boo[n]; for(i=0;i
yes it is. proof: let us assume n is divisible by i*j where j < i So if (i*j) can divide or lets say cancel out n then n should have been cancelled out by j (because j is less than i). Thus not possible
@@kartikprakash4681 Okay I can explain you, lets say we're currently computing for 13 13 * 2 = 26 (As it is 13*2, it becomes multiple of 2, so it would get striked while executing i = 2) 13 * 3 = 39 (now 13 becomes multiple of 3 , so it would striked whiile executing i = 3) 13 * 4 = .... (striked while executing i = 2) 13 * 5 = .... (striked while executing i = 5) 13 * 6 = .... (striked while executing i = 2) 13 * 7 = .... (striked while executing i = 7) 13 * 8 = .... (striked while executing i = 2) 13 * 9 = .... (striked while executing i = 3) 13 * 10 = .... (striked while executing i = 2) 13 * 11 = .... (striked while executing i = 11) 13* 12 = ....(striked while executing i = 2) 13 * 13 = From here you need to start executing again Hope this helps !
j = i would be fine becoz For example, lets say we're currently computing for 13 13 * 2 = 26 (As it is 13*2, it becomes multiple of 2, so it would get striked while executing i = 2) 13 * 3 = 39 (now 13 becomes multiple of 3 , so it would striked whiile executing i = 3) 13 * 4 = .... (striked while executing i = 2) 13 * 5 = .... (striked while executing i = 5) 13 * 6 = .... (striked while executing i = 2) 13 * 7 = .... (striked while executing i = 7) 13 * 8 = .... (striked while executing i = 2) 13 * 9 = .... (striked while executing i = 3) 13 * 10 = .... (striked while executing i = 2) 13 * 11 = .... (striked while executing i = 11) 13* 12 = ....(striked while executing i = 2) 13 * 13 = From here you need to start executing again Hope this helps !
better if we use boolean array than integer it will save some time while printing the array ! void sieve(int n) { bool prime[n+1]; memset(prime,true,sizeof(prime); for(int i=2;i*i
@@utsavprabhakar5072 Yeah, this video/algorithm is very very basic, there are many more optimizations on this. There is one simple (implementation wise) extension to get linear complexity as well..
He has initially assumed all the numbers from 0 to n are prime, then as we know 0 and 1 are not prime so he make them 0 and then he start the loop taking i=2 to n , i hope u understood
The first algorithm's time complexity is lesser than O(n^3/2). The inside loop has complexity sqrt(i) each time(not sqrt(n)). So it will be something like sqrt(2) + sqrt(3) + .....sqrt(n). Don't know the sum but should be lesser than n^3/2.
the elements in the array may not be set as zero just with the declaration. So, anyway we would have to set value explicitly. But yes, we could do it differently.
Thank you for this video :D !!! Just one question, I saw an implementation that only started marking off numbers starting from that number squared rather than from that number times 2 like you did in this video. (example: when you get to 3 and see that it is a prime you start marking from 9 rather than 6 because 6 would just be 3 times 2 and you already marked off all the multiples of 2) Is that a correct way to implement this?
How could we know the number of loops we have to use in this program. As u have used if loop and for loop what's the difference and when to use both of them ???
if we are setting every array element of size n with value 1, what are we at end returning? why do we make whole array of value 1? Also, time complexity = O(n * log log n) + O(n) where, O(n) is highest among two, won't the complexity of whole program will be O(n)? About O(n* log log n ) if we are looping for sqrt(n), should not this to go by = O(sqrt(n) * log log n) ?! If we making whole array made up of 1, and looping through only sqrt(n), from where & what we will return as final output?eg n=100 & sqrt=10 then from where a prime numbers beyond sqrt(n) to be returned?
in analysis of trial division we will get something like, n^1/2+(n-1)^1/2+(n-2)^1/2.....(n-(n-2))^1/2 how can we get ur result n(root n) from this pls tell if i m wrong (i m bad at this) tnx
I dont understand which part of the code checks whether a number is prime or not? I only see code to mark numbers off, where is the actual finding whether 2 or 3 is prime or not ?
I've created the array of size 1000 but my program can't calculate the prime numbers higher than 125 that means only 30 prime numbers..if it exceeds 30 then program terminates with an option to debug. I m not able to understand what's wrong in it.
because we need to include "nth" number/index....ie...index stars from 0....so if n=4 and prime[4] then it will create total of n-1 index ...0th 1st 2nd 3rd...n=4 and prime[4+1] we'll get 0th 1st 2nd 3rd 4th total index hope you get the point.
I'm pretty sure that's because array's are starting from 0 to n-1. so if ur n (the prime number you want to check) is 15 for example and you make an array of 15 cells so you will get 0-14 cells (that's 15 cells starting from 0). so you want to create a 16 cells array (starting from 0 to 15) in order to check if 15 is prime. hope you get it.
You want to include it because it's gonna get "crossed out" if it's not a prime. All numbers are divisible by themselves, what we're looking for is if they're divisible by any number that comes before them (other than 1).
To apply the logic in the user-defined range you can approach the segmented sieve concept. Follow the link: www.geeksforgeeks.org/segmented-sieve-print-primes-in-a-range/
it is a loop used to initialize the array primes to 1, that means it is used to assign each element of the array primes to 1. making primes[0] = 1, primes[1] = 1 ..... primes[n] = 1. and later when we use the algorithms, the only numbers that are prime will have a value of 1 at its corresponding index.
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
Best video I've found about the Sieve of Eratosthenes so far! Great work!
+David Hariri Do you have a video that compares the complexities of all major prime factorization algorithms (including brute division)?
@@dhariri ua-cam.com/video/7CyBf-xZF4c/v-deo.html
@@sriram8027 I guess he might have figured that out within this 4 years.
Hey just reminding u it's been 6 year's 😂
8:40 for i=2, we are striking off 6 elements. Here n=15, and n/2 !=6. can you please explain how n/2 n/3 ... ?
We can further optimize by reducing the number of unwanted strikes.
If i and j are co-factors of number n i.e j x i = n , then there is no need to strike off multiples of i which are < i*i (square of i ) where j < i
In other words the for loop for j can start at i ( when i=3 , j can start at 3 instead of 2 , because the multiples of i < (i*i) i.e for multiples of i
start j with i *i , you will optimise it even further.
then what will be the time complexity?
@@aor6956 I was going to say this for those who are wondering about the proof here goes:
you might think this Gentleman has asked you to skip numbers from i*2-i*(i-1) for each i but if you observe all these numbers have already been marked of by numbers from 2 to (i-1) for which we have already marked the sieve. Therefore we can start from j = i*i and still get away with it.
@@VarsneyaSrinivas j=i*i will work. But how to prove it??
I homeschool, but I knew the equation. However, I can't teach something if I can't explain it. I've been looking but none explained it so well to me. Now I can explain it to someone else. Thank you for taking your time to give a very good explanation.
Rest in piece! You will be remembered forever through your excellent teaching🤎
Thanks a lot. Very very helpful lessons!
I`ve noticed something confusing in 3:01. "If 2 is prime, then all multiples of 2 cannot be prime". Actually, any multiple of any positive integer cannot be prime, no matter if the factor is prime. Please let me know if I`m missing something.
say for eg take 4 as it is not prime and its factor is 2 .and every multiple 0f 4 will already be cancelled by the multiple of 4.
for any grid that is a square, you only need to work out the first row of numbers. the numbers left uncrossed in the grid will be primes.
so for n=1,000,000, you only need to work out the first row of 1,000 to find every prime in the 1,000x1,000 grid.
Thank you, Your legacy lives on Harshal
I propose much more simplier "matrix sieve" algorithm for finding prime numbers:
In order to find all primes (up to a given limit) in the sequence S1(p)=6p+5,(p=0,1,2,3,...):
Step 1a. Starting from 5 cross out each 5th member of the row of positive integersN(n)=0,1,2,3,4..., i.e remove the following integers: 5, 10, 15,...
Step 1b. Starting from 5 cross out each 7th member of the row of positive integers, i.e remove the following integers: 5, 12, 19,..
Step 2a.Starting from 23 cross out each 11th member of the row of positive integers, i.e remove the following integers: 23, 34, 45,...
Step 2b. .Starting from 23 cross out each 13th member of the row of positive integers, i.e remove the following integers 23, 36, 49,...
.........
Step ia. Starting from (6i^2−1) cross out each (6i−1)th member of the row of positive integers.
Step ib. Starting from (6i^2−1) cross out each (6i+1)th member of the row of positive integers.
Remaining members of N(n) are indexes p of all primes (up to a given limit) in the sequence S1(p)=6p+5: p=0,1,2,3,4,...,6,7,8,9,...,11,..,13,14,....,16.....p=and primes are 5,11,17,23,29,...,41,47,53,59,...,71,...,83,89,...
In order to find all (up to a given limit) primes in the sequence S2(p)=6p+7,(p=0,1,2,3,...):
Step 1a. Starting from 3 cross out each 5th member of the row of positive integers, i.e remove the following integers 3,8,13,...
Step 1b. .Starting from 7 cross out each 7th member of the row of positive integers, i.e remove the following integers 7,14,21,...
Step 2a.Starting from 19 cross out each 11th member of the row of positive integers, i.e remove the following integers 19,30,41,...
Step 2b. .Starting from 27 cross out each 13th member of the row of positive integer, i.e remove the following integers 27,40,53,...
.........
Step ia.Starting from (6i^2−1−2i) cross out each (6i−1)th member of the row of positive integers.
Step ib.Starting from (6i^2−1+2i) cross out each (6i+1)th member of the row of positive integers.
Remaining members of N(n) are indexes p of all primes (up to a given limit) in the sequence S2(p)=6p+7: p=0,1,2,..,4,5,6,..,9,10,11,12,...,15,16.... and primes are7,13,19,...,31,37,43,...,61,67,73,79,...,97,103,...
C++ program:
www.planet-source-code.com/vb/scripts/BrowseCategoryOrSearchResults.asp?lngWId=3&blnAuthorSearch=TRUE&lngAuthorId=21687209&strAuthorName=Boris%20Sklyar&txtMaxNumberOfEntriesPerPage=25
Boris Sklyar this is pretty cool, how'd you come up with this? What is the time complexity?
@@josevillegas2721 : you would have found this already, but it's there in CLRS book
best channel for data structures
T(n) would be sqrt(n)log log n. Explanation was correct. Just a typo.
couldn't be. We're setting each value of primes as -1 for (n+1) times so it's O(nloglogn)
@@ankitsharma8221 Which is set part in the outer loop. The overall complexity is O(n^0.5 * log log n) + O (n)
I have been trying to find the most optimized method to find prime numbers.
Yours was most efficient and easiest to understand so far.
Upon experimenting, I found a more optimised solution.
In second nested for loop where j starts from 2.
we multiply j to i where i starts from 2 -> sqrt(n)
Instead of using 2 we can set j = i in the second nested loop
lets say i = 5 and j = 2 as of now
but since 5 * 2 = 10, 5 * 3 = 15 , 5 * 4 = 20 where 10, 15, 20 are already covered by 2 and 3 respectively. there is no need to override those 0 from Prime[] array.
we could directly go to 5 * 5 where 25 isnt marked yet 0.
What can be the time complexity of this new approach?
#include
#include
using namespace std;
int main()
{
cout.sync_with_stdio(false);
unsigned long int n = 100000;
unsigned long int i,j;
int boo[n];
for(i=0;i
Time complexity will still be the same i.e. O(n*log logn)
Excellent! Even I want to know the time complexity of this algorithm.
Searching for a good video on seive method. found the best one
Is it not possible to run the second for loop from j = i instead of starting from 2?
yes it is.
proof: let us assume n is divisible by i*j where j < i
So if (i*j) can divide or lets say cancel out n then n should have been cancelled out by j (because j is less than i).
Thus not possible
yes...infact the second loop IS started from j=i*i that's how we get the required time complexity....he made a mistake in the video
If used square root of n and j=i*i;j
Actually you can have a variable inside an array subscript in C/C++, given the variable is already initialized
The condition for second loops is "i*j
You didn't understood the algorithm properly,let's say 18 which is not a prime must have been struck off by any no. less than sqrt(18).
Loved the way you explained and the optimization part as well thank you
You can optimise even more by changing the initialization in the inner loop. Instead of:
j = 2
use
j = i
Exactly!
How will that make sure that we are striking off every multiple of i? Correct me if i am wrong :)
@@kartikprakash4681 Okay I can explain you, lets say we're currently computing for 13
13 * 2 = 26 (As it is 13*2, it becomes multiple of 2, so it would get striked while executing i = 2)
13 * 3 = 39 (now 13 becomes multiple of 3 , so it would striked whiile executing i = 3)
13 * 4 = .... (striked while executing i = 2)
13 * 5 = .... (striked while executing i = 5)
13 * 6 = .... (striked while executing i = 2)
13 * 7 = .... (striked while executing i = 7)
13 * 8 = .... (striked while executing i = 2)
13 * 9 = .... (striked while executing i = 3)
13 * 10 = .... (striked while executing i = 2)
13 * 11 = .... (striked while executing i = 11)
13* 12 = ....(striked while executing i = 2)
13 * 13 = From here you need to start executing again
Hope this helps !
@@kausachan4167 well explained
Nice explanation 😊👏
j = i would be fine becoz
For example, lets say we're currently computing for 13
13 * 2 = 26 (As it is 13*2, it becomes multiple of 2, so it would get striked while executing i = 2)
13 * 3 = 39 (now 13 becomes multiple of 3 , so it would striked whiile executing i = 3)
13 * 4 = .... (striked while executing i = 2)
13 * 5 = .... (striked while executing i = 5)
13 * 6 = .... (striked while executing i = 2)
13 * 7 = .... (striked while executing i = 7)
13 * 8 = .... (striked while executing i = 2)
13 * 9 = .... (striked while executing i = 3)
13 * 10 = .... (striked while executing i = 2)
13 * 11 = .... (striked while executing i = 11)
13* 12 = ....(striked while executing i = 2)
13 * 13 = From here you need to start executing again
Hope this helps !
8:40 for i=2, we are striking off 6 elements. Here n=15, and n/2 !=6. can you please explain how n/2 n/3 ... ?
your explanation is so great
Really good explanation!
thank you for explaining the logic of using sqrt(n). Noone else has explained this logic.
Thank you very much. 👍 👍🔝🔝🙏🙏
Thank you so much.Really great explanation.
You are doing a great Job man!
better if we use boolean array than integer it will save some time while printing the array !
void sieve(int n)
{
bool prime[n+1];
memset(prime,true,sizeof(prime);
for(int i=2;i*i
Great video. But wikipedia seems to have one more optimization , at every prime it seems to start cancelling it's multiples from i^2 onwards...
Yep i saw that. Optimisations never end!
@@utsavprabhakar5072 Yeah, this video/algorithm is very very basic, there are many more optimizations on this.
There is one simple (implementation wise) extension to get linear complexity as well..
Amazing video. Great work :)
best video on Sieve of Eratosthenes :)
Can you please explain the meaning of the line at 5:03, i'm not getting it even after watching it several times.
Its a humble request!
He has initially assumed all the numbers from 0 to n are prime, then as we know 0 and 1 are not prime so he make them 0 and then he start the loop taking i=2 to n , i hope u understood
best explained the sieve in a short duration...
clearly explained, good work !!!
This is nice video, in the inner for loop, if j is initialized to i, we can save some more loops.
The first algorithm's time complexity is lesser than O(n^3/2). The inside loop has complexity sqrt(i) each time(not sqrt(n)). So it will be something like sqrt(2) + sqrt(3) + .....sqrt(n). Don't know the sum but should be lesser than n^3/2.
the first loop could also start from 2 instead?
the elements in the array may not be set as zero just with the declaration. So, anyway we would have to set value explicitly. But yes, we could do it differently.
@@mycodeschool we are not using index 0 or 1 so it will not effect i think
Thank you for this video :D !!! Just one question, I saw an implementation that only started marking off numbers starting from that number squared rather than from that number times 2 like you did in this video. (example: when you get to 3 and see that it is a prime you start marking from 9 rather than 6 because 6 would just be 3 times 2 and you already marked off all the multiples of 2) Is that a correct way to implement this?
Superb explanation
waaaoo man ...so simplified...kudossssss
good explanations. Thank u so much Sir
awesome. python list size limit is ruining the problem to solve largest prime factor of a really large number using this method
Subtitles hide the contents which u write down the white board
Will you please a upload a video on segmented sieve too..
I have a qus here.If at first we set all the elements in the array equal to 1,how the real numbers exists in the array?
we are checking the indices of the array not their values
the first loop runs for (n-1) times why use O(n*sqrtn), and not O(n-1)*sqrtn for the time complexity
Valid point, I think he meant that, just slipped up
That doesnt matter ... Compiler will take same time in both of them
(N-1)*sqrt(N)= N*sqrt(N) - sqrt(N)
That sqrt(N) doesnt improve the time complexity
Thank you. Great explanation. :)
Please make video for time complexity of o(n)
i.e. manipulated version of eratosthanes
How could we know the number of loops we have to use in this program. As u have used if loop and for loop what's the difference and when to use both of them ???
I'd is just a conditional statement not a loop
@@RudraSingh-pb5ls ok thanks
if we are setting every array element of size n with value 1, what are we at end returning? why do we make whole array of value 1?
Also, time complexity = O(n * log log n) + O(n) where, O(n) is highest among two, won't the complexity of whole program will be O(n)?
About O(n* log log n ) if we are looping for sqrt(n), should not this to go by = O(sqrt(n) * log log n) ?!
If we making whole array made up of 1, and looping through only sqrt(n), from where & what we will return as final output?eg n=100 & sqrt=10 then from where a prime numbers beyond sqrt(n) to be returned?
ua-cam.com/video/7CyBf-xZF4c/v-deo.html
+mycodeschool can you make a video specially of O(N) & theta(N) complexity?!
Where are you now? Why do you stop making videos? Please come back and start making videos again.
We lost him unfortunately in an accident
@@sriram8027 What!! seriously?
@@nomaannafi1093 yourstory.com/2014/06/techie-tuesdays-humblefool
One of the co founder is no more
easiest explanation i found on internet
I got the concept...but still not the code....so do I cram it or try understanding the code.....if u can help me with it....😦😦😦..pls
the outer loop starts from 2 - till n so the outer loop runs n-1 times so ignoring the constant n times*sqrt(n)
if i am correct???
in analysis of trial division we will get something like,
n^1/2+(n-1)^1/2+(n-2)^1/2.....(n-(n-2))^1/2
how can we get ur result n(root n) from this
pls tell if i m wrong (i m bad at this)
tnx
I dont understand which part of the code checks whether a number is prime or not? I only see code to mark numbers off, where is the actual finding whether 2 or 3 is prime or not ?
best video but variable or expression we can use as a size in array in c/cpp.
i see another optimization here you can make the second loop increment by j+=i rather than j++
i dont think so, we are eliminating all the multiples of i, and using j as a multiplier for every next element of i
Your method is valid if we are just taking the conditions in j instsed of involving i
Very clear :) Thank you!
I've created the array of size 1000 but my program can't calculate the prime numbers higher than 125 that means only 30 prime numbers..if it exceeds 30 then program terminates with an option to debug. I m not able to understand what's wrong in it.
when you are already starting loop from 2 then why you are checking if prime[i]==1 .you have already skipped 0 and 1
Subtitles are covering the content of page please try to solve this problem in future videos
thats a problem only youtube can solve
turn off the subtitles
why using prime[n+1} instead of prime[n]?
because we need to include "nth" number/index....ie...index stars from 0....so if n=4 and prime[4] then it will create
total of n-1 index ...0th 1st 2nd 3rd...n=4 and prime[4+1] we'll get 0th 1st 2nd 3rd 4th total index hope you get the point.
crystal and clear!Thanks :D
Wildly wrong bounds for the loops.
i := 0..sqrt(n) and
j:= i*i...n+1 increment by i
Why not O( sqrt(n).loglog(n) ) ?
Thank you sir.
Why stopped uploading video we need your video
We lost him in an accident
May I know why we define array of N+1 size rather than size N?
I'm pretty sure that's because array's are starting from 0 to n-1.
so if ur n (the prime number you want to check) is 15 for example and you make an array of 15 cells so you will get 0-14 cells (that's 15 cells starting from 0).
so you want to create a 16 cells array (starting from 0 to 15) in order to check if 15 is prime.
hope you get it.
I thought you don't wanna check the the n number because it's obviously divisible by itself.
because we need to include index N (which represents our number N)
You want to include it because it's gonna get "crossed out" if it's not a prime. All numbers are divisible by themselves, what we're looking for is if they're divisible by any number that comes before them (other than 1).
Please make a video on Segmented Sieve @mycodeschool
Can anyone tell me if this applies for any ranges or just starting from 1 to n
To apply the logic in the user-defined range you can approach the segmented sieve concept.
Follow the link: www.geeksforgeeks.org/segmented-sieve-print-primes-in-a-range/
is this the voice of lord harshal??
what if you want to get the prime number between a two number? e.g 100 - 200
Call the method twice: return method(200) - method(100)
Can someone help me reduce the space complexity please
Thanks.
How to initialise array[n+1 in c++ ????
use std::array if size is already known
Big theta or big oh???
for(int i=0;i
it is a loop used to initialize the array primes to 1, that means it is used to assign each element of the array primes to 1.
making primes[0] = 1, primes[1] = 1 ..... primes[n] = 1.
and later when we use the algorithms, the only numbers that are prime will have a value of 1 at its corresponding index.
I don't understand the "code implementation" part :(
bro ignore it. It is just pseudo code(just English like code :D)
in place of first for loop u can use
max =10000;
bool arr[max]={1};
oh
thank you
ua-cam.com/video/0ABnO_WoexE/v-deo.html
를 이용하여
1부터 1,000까지 사이에 있는
소수의 개수(counting prime numbers)를 구하는 영상 입니다.
Running the programme on the computer would have been better. Still thanks for the video. Really good one about topic.
thank u sir
nested for loop is wrong giving wrong output .It should be
for(int i=2;i
thank u
awesome
Here is the Program code:
ua-cam.com/video/sx3Cw14XZoc/v-deo.html
great
2:25
Please say slowly not so fast sir
who the fuck uses pen and pencil to code
: (I hate it
If i want to see the output like
1 0
2 1
3 1
4 0
How can i write the code
Thank you
2:35
Thank you