Finding Prime numbers - Sieve of Eratosthenes

[@dhariri]

Best video I've found about the Sieve of Eratosthenes so far! Great work!

[@dhariri]

+David Hariri Do you have a video that compares the complexities of all major prime factorization algorithms (including brute division)?

[@sriram8027]

@@dhariri kzbin.info/www/bejne/bXTcc5ljrb95asU

[@aqua6150]

@@sriram8027 I guess he might have figured that out within this 4 years.

[@venki2432]

Hey just reminding u it's been 6 year's 😂

[@gaganbedi4332]

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 ... ?

[@deh773]

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.

[@sr5726]

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]

start j with i *i , you will optimise it even further.

[@shivanshbhardwaj5841]

then what will be the time complexity?

[@VarsneyaSrinivas]

@@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.

[@chagantisubhash2456]

@@VarsneyaSrinivas j=i*i will work. But how to prove it??

[@adeebahmed1067]

​@@shivanshbhardwaj5841 1.Time Complexity: O(nlogn logn) Marking multiples of a prime takes O(logn) iterations. Since there are approximately n/logn primes up to n, this leads to the overall complexity of O(nlog logn) 2.Space Complexity: O(n)O(n) We store a boolean list of size n+1.

[@alexanderpetranov]

Rest in piece! You will be remembered forever through your excellent teaching🤎

[@SYLperc]

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.

[@TomLobato]

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.

[@abhishiekmahajan9103]

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.

[@AtifShafiinheritance]

best channel for data structures

[@manaswitadatta]

T(n) would be sqrt(n)log log n. Explanation was correct. Just a typo.

[@ankitsharma8221]

couldn't be. We're setting each value of primes as -1 for (n+1) times so it's O(nloglogn)

[@mohitranka9840]

@@ankitsharma8221 Which is set part in the outer loop. The overall complexity is O(n^0.5 * log log n) + O (n)

[@maheshvangala8472]

Searching for a good video on seive method. found the best one

[@sanjayidpuganti8367]

Actually you can have a variable inside an array subscript in C/C++, given the variable is already initialized

[@herzalla9]

If used square root of n and j=i*i;j

[@borissklyar1415]

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

[@josevillegas2721]

Boris Sklyar this is pretty cool, how'd you come up with this? What is the time complexity?

[@PabitraPadhy]

@@josevillegas2721 : you would have found this already, but it's there in CLRS book

[@AshutoshTiwari0]

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

[@saifrehman2776]

Time complexity will still be the same i.e. O(n*log logn)

[@aarushiaiyyar]

Excellent! Even I want to know the time complexity of this algorithm.

[@sidddddddddddddd]

The condition for second loops is "i*j

[@SHUBHAMKUMAR-zc5ns]

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).

[@rajeshgopidi7842]

Is it not possible to run the second for loop from j = i instead of starting from 2?

[@AmitCodes]

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

[@visheshkumar7812]

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

[@lomeshdaheria9960]

Loved the way you explained and the optimization part as well thank you

[@rishabhmalhotra1317]

Thank you, Your legacy lives on Harshal

[@tomasz-rozanski]

You can optimise even more by changing the initialization in the inner loop. Instead of: j = 2 use j = i

[@Advanta09]

Exactly!

[@kartikprakash4681]

How will that make sure that we are striking off every multiple of i? Correct me if i am wrong :)

[@kausachan4167]

​@@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 !

[@AyushRaj-pm1dz]

@@kausachan4167 well explained

[@gaganbedi4332]

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 ... ?

[@kausachan4167]

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 !

[@hujingtao1]

your explanation is so great

[@pranjalgupta9427]

Nice explanation 😊👏

[@malharjajoo7393]

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...

[@utsavprabhakar5072]

Yep i saw that. Optimisations never end!

[@malharjajoo7393]

@@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..

[@pookie-dev]

Really good explanation!

[@sreekumarmenon]

the first loop could also start from 2 instead?

[@mycodeschool]

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.

[@abhinavgupta6743]

@@mycodeschool we are not using index 0 or 1 so it will not effect i think

[@maheshvshet]

This is nice video, in the inner for loop, if j is initialized to i, we can save some more loops.

[@RishabhLohia3]

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.

[@SmokyBigSmoke]

Thank you so much.Really great explanation.

[@kushsharma3716]

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!

[@AryanSinghBCS]

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

[@hmt001]

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?

[@vakhariyajay2224]

Thank you very much. 👍 👍🔝🔝🙏🙏

[@arjunm8431]

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???

[@shaikjareena797]

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 ???

[@RudraSingh-pb5ls]

I'd is just a conditional statement not a loop

[@shaikjareena797]

@@RudraSingh-pb5ls ok thanks

[@94D33M]

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 ?

[@iaktech]

You are doing a great Job man!

[@sarcaastech]

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

[@ashiqimran5961]

clearly explained, good work !!!

[@anshumangaur7290]

best video on Sieve of Eratosthenes :)

[@namrataswain7999]

Amazing video. Great work :)

[@shubhamtripathi7928]

Will you please a upload a video on segmented sieve too..

[@rajkesharwani4344]

Subtitles hide the contents which u write down the white board

[@letsthinkit6015]

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?

[@ashutoshpawade8570]

we are checking the indices of the array not their values

[@ManojSaini_15]

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.

[@gladyouseen8160]

Please make video for time complexity of o(n) i.e. manipulated version of eratosthanes

[@parasmalhotra7633]

best explained the sieve in a short duration...

[@dhruva1221]

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?

[@sriram8027]

kzbin.info/www/bejne/bXTcc5ljrb95asU

[@rishabhjain2404]

thank you for explaining the logic of using sqrt(n). Noone else has explained this logic.

[@ekhliousful]

+mycodeschool can you make a video specially of O(N) & theta(N) complexity?!

[@Aniket7Tomar]

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

[@SunilSingh1994]

good explanations. Thank u so much Sir

[@JohnnyKnight5talker]

awesome. python list size limit is ruining the problem to solve largest prime factor of a really large number using this method

[@Hampirathna]

Superb explanation

[@rayalubaggi]

best video but variable or expression we can use as a size in array in c/cpp.

[@obentabiayuk4780]

the first loop runs for (n-1) times why use O(n*sqrtn), and not O(n-1)*sqrtn for the time complexity

[@amuzakishikawa3730]

Valid point, I think he meant that, just slipped up

[@manthankhorwal1477]

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

[@dunnowut7005]

May I know why we define array of N+1 size rather than size N?

[@shmolik930]

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.

[@dunnowut7005]

I thought you don't wanna check the the n number because it's obviously divisible by itself.

[@philtrem]

because we need to include index N (which represents our number N)

[@philtrem]

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).

[@RudraSingh-pb5ls]

Why not O( sqrt(n).loglog(n) ) ?

[@nomaannafi1093]

Where are you now? Why do you stop making videos? Please come back and start making videos again.

[@sriram8027]

We lost him unfortunately in an accident

[@nomaannafi1093]

@@sriram8027 What!! seriously?

[@sriram8027]

@@nomaannafi1093 yourstory.com/2014/06/techie-tuesdays-humblefool

[@sriram8027]

One of the co founder is no more

[@utkarshsingh3541]

waaaoo man ...so simplified...kudossssss

[@hassanmahmoud9035]

i see another optimization here you can make the second loop increment by j+=i rather than j++

[@arten3328]

i dont think so, we are eliminating all the multiples of i, and using j as a multiplier for every next element of i

[@pi_rand4266]

Your method is valid if we are just taking the conditions in j instsed of involving i

[@ShaeekhShuvro]

why using prime[n+1} instead of prime[n]?

[@Akash-kq8lm]

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.

[@ShaeekhShuvro]

crystal and clear!Thanks :D

[@prashantdas5554]

Thank you. Great explanation. :)

[@Alfafoxtrot001]

when you are already starting loop from 2 then why you are checking if prime[i]==1 .you have already skipped 0 and 1

[@adithyasundar8904]

Can anyone tell me if this applies for any ranges or just starting from 1 to n

[@ayanbiswas6849]

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/

[@kushagragupta4259]

Subtitles are covering the content of page please try to solve this problem in future videos

[@lootnation6276]

thats a problem only youtube can solve

[@surabhisharma6608]

turn off the subtitles

[@KanagaveluSugumar]

Very clear :) Thank you!

[@Atpugtihsrah]

Please make a video on Segmented Sieve @mycodeschool

[@emmaautumn4666]

what if you want to get the prime number between a two number? e.g 100 - 200

[@TheGalactus16]

Call the method twice: return method(200) - method(100)

[@mahabubara1641]

I don't understand the "code implementation" part :(

[@pranavkrishna4413]

bro ignore it. It is just pseudo code(just English like code :D)

[@michaelkaufman5119]

Wildly wrong bounds for the loops. i := 0..sqrt(n) and j:= i*i...n+1 increment by i

[@20_atulsingh57]

Why stopped uploading video we need your video

[@sriram8027]

We lost him in an accident

[@rohankumar-of5qe]

How to initialise array[n+1 in c++ ????

[@PabitraPadhy]

use std::array if size is already known

[@primakovch8332]

Big theta or big oh???

[@ivyzheng8681]

Thank you sir.

[@nishantingle1438]

Can someone help me reduce the space complexity please

[@nakibtheexplorer5383]

for(int i=0;i

[@arten3328]

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.

[@ravisinha1310]

is this the voice of lord harshal??

[@ok.tanmay]

easiest explanation i found on internet

[@Shelly888-s1r]

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

[@yasahanzengin3329]

Thanks.

[@shahidabegum548]

oh

[@Ali-Intakhab]

in place of first for loop u can use max =10000; bool arr[max]={1};

[@kirubagaran3749]

thank you

[@pranavkrishna4413]

awesome

[@sonukumarprashant]

nested for loop is wrong giving wrong output .It should be for(int i=2;i

[@mitultyagi3357]

Running the programme on the computer would have been better. Still thanks for the video. Really good one about topic.

[@devanshgoel3433]

thank u sir

[@seraj_valley]

great

[@tv..6531]

kzbin.info/www/bejne/ZnKln4KVjNSYrqc 를 이용하여 1부터 1,000까지 사이에 있는 소수의 개수(counting prime numbers)를 구하는 영상 입니다.

[@wassup102]

thank u

[@pratikshinde3402]

2:25

[@reshmianil4638]

Please say slowly not so fast sir

[@bharathiDevi001]

Here is the Program code: kzbin.info/www/bejne/qamWdKpnab2NpcU

[@travistarp7466]

who the fuck uses pen and pencil to code

[@jaydanplaza]

: (I hate it

[@mahbubaurko8764]

If i want to see the output like 1 0 2 1 3 1 4 0 How can i write the code

[@anuraganand7783]

Thank you

[@preetamvarun9219]

2:35

[@Mythri333]

Thank you