If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content
Current time:0:00Total duration:4:12

Video transcript

I'm now going to introduce an ancient method for generating a list of primes up to some limit n called the sieve of eratosthenes now Eratosthenes was born in 276 BC so this method you know is over 2200 years old but it's very simple and elegant and you could teach it to any child now let's say for example we want to calculate all the primes up to 100 but this would work in the same way if we wanted to calculate up to 10,000 or a billion it proceeds as follows assume all numbers are unmarked gray is unmarked we start at the beginning and if we find a number that is unmarked we know its prime so we hit 2 and we say 2 is prime because it's unmarked and then the second phase is now we can eliminate all multiples of 2 because we know they're composite so BAM we jump along and we eliminate all multiples 2 of 2 red means composite and now we repeat we step along from 2 to 3 3 is unmarked so we mark 3 is prime and now we can eliminate all multiples of 3 and a really simple optimization as notice 6 is already crossed off we actually cross off the multiples starting at the square of that number so 3 times 3 is 9 we start at 9 and Mark all multiples of 3 as composite and again we go back we jump along to 4 well 4 is marked we know it's composite and we jump along to 5 we found an unmarked number 5 is prime now 5 times 5 is 25 we go to 25 we mark off 25 30 35 40 45 and so on those are composites we proceed forward until we hit 7 we know 7 is prime because it's unmarked 7 times 7 is 49 we mark 49 and all multiples of 7 above it as composite and now we move along until we hit 11 11 is prime and notice now 11 times 11 is greater than 100 so we actually stop at this point we could have stopped at ten even because now all remaining unmarked numbers if you'll notice our prime and we could in one swoop mark them all as Prime and that's the whole algorithm it's so simple and just to generalize how we do this so we could write up a program to perform this SIV is if we want to find all Prime's up to some number n we first create a main loop so we have for all numbers a from 2 to the square root of n so notice here we stopped when we hit 10 or if I showed it as 11 we actually stopped because we have found all Prime's so from 2 to the square root of n we proceed as follows if a is unmarked then we know a is prime and when we find a prime number we mark all multiples of a off as composite and that's it so you find a number prime mark off the multiples go back to the beginning increment a by 1 so we're on 2 then we go to 3 then we go to 4 or 5 and so on and when we're done we have all Prime's notice here that this is also a loop so we have a main loop 4 and when we find a prime this marking off of multiples is also a loop so it's important to notice here that we have a nested loop we have a loop inside a loop here is an example of this algorithm in action I wrote in JavaScript below if I put in 100 here are all the primes under 100 and if I put in 200 here are all the primes under 200 and if I put in 850 here are all the primes under 850 and below I have this program with the recording explaining how I set it up