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

Sieve of Eratosthenes

Sieve of Eratosthenes allows us to generate a list of primes. Created by Brit Cruise.

Want to join the conversation?

  • mr pink red style avatar for user brit cruise
    (45 votes)
    Default Khan Academy avatar avatar for user
    • aqualine ultimate style avatar for user Joel Alexander
      Every number that's a multiple of n and some other number smaller than n has already been crossed off, because we crossed off all the multiples of numbers smaller than n before we started looking at n. If that makes any sense.

      To give an example, if n = 5, we've already crossed off 10 (because it's 2*5 and we crossed off multiples of 2 when we were looking at 2), and 15 (because it's 3*5 and we crossed off multiples of 3 when we were looking at 3), and 20 (because it's 2*2*5 and we crossed off multiples of 2 when we were looking at 2). This means that 25 = 5*5 is the first multiple of 5 that hasn't already been crossed off.

      Essentially, n*n is the smallest multiple of n that we haven't already eliminated from consideration. Not sure if I can prove that mathematically, but there's your logic proof.
      (10 votes)
  • mr pants teal style avatar for user Hollerdog
    This may be a silly question, can a negative number be prime? For example, -3,-5,-7 etc
    (14 votes)
    Default Khan Academy avatar avatar for user
  • mr pants teal style avatar for user Baba Spickoli
    How do we know it's ok to stop at the sqrt of (N), and that we've found all primes? Is there a law or proof? Or is the Sieve of Eratosthenes the proof? If N = 99, do we round its square root up?
    (6 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Suppose I was looking for the factors of a number N

      Let's say I check the factors starting at 1 and then go up by 1 each step
      1 would be a factor and N would be a matching factor
      if 2 was a factor then N/2 would be a matching factor
      if 3 was a factor then N/3 would be a matching factor
      ....
      if (x) was a factor then (N/x) would be a matching factor. (since x*(N/x)=N)
      before I get to x=sqrt(N) the numbers on the left are smaller than the numbers on the right
      Now I get to x=sqrt(N).
      If (sqrt(N)) was a factor then (sqrt(N))would be a matching factor
      now the numbers are the same size on the left and the right
      If I keep going the numbers on the left will be bigger than the numbers on the right.

      Do I need to keep checking ?
      Well let's suppose I did need to keep checking.
      I would only need to keep checking if there existed a factor,that wasn't on my left side AND wasn't a matching factor.
      Let's call this factor y. Then it's matching factor would be (N/y).
      But y is bigger than the square root of N.
      So it's matching factor (N/y) must be smaller than the square root of N.
      But I've already checked ALL the numbers smaller than the square root of N !
      So this can't be a factor/matching factor I haven't checked already.
      So since it is impossible to find a factor,matching factor pair that I haven't already checked, I don't need to bother checking past sqrt(N).

      The above doesn't matter if we are looking for composite factors or prime factors.

      Now for the sieve.....
      If I was looking for all the factors of 2 I would only need to look for numbers <= sqrt(2)
      If I was looking for all the factors of 3 I would only need to look for numbers <= sqrt(3)
      If I was looking for all the factors of 4 I would only need to look for numbers <= sqrt(4)
      ....
      If I was looking for all the factors of 100 I would only need to look for numbers <= sqrt(100)

      If we didn't find any factors (other than 1 and itself) before we reach sqrt(N) then the number must be prime.
      By marking off all the multiples of the number when we do the sieve, we check if that number is a factor, for all the numbers larger than it.
      So once we hit 10 on the sieve, we have checked all the factors <=sqrt(N) for every number <=100.

      If we haven't found a factor for those numbers yet, it doesn't exist.

      Hope this makes sense.
      (17 votes)
  • mr pants teal style avatar for user Hollerdog
    Why do we want to know if one or more numbers are prime?
    (6 votes)
    Default Khan Academy avatar avatar for user
    • leaf red style avatar for user DEHD93
      Primes are one mysterious thing that humans have been studying all around history. Prime numbers behavior is one of the basics and less understand things on Mathematics. Basically primes are the structure of numbers, understanding primes is like understanding the universe, 4th dimension... That is why understanding primes is such an important branch of Mathematics.
      (13 votes)
  • hopper cool style avatar for user Colin
    Why do I hear about the answer being 42 everywhere? I cannot think of any special properties this number has, as it is not a perfect square, not a prime number, and not a Fibonacci number. What does it mean/stand for?
    (4 votes)
    Default Khan Academy avatar avatar for user
    • mr pink red style avatar for user Varun
      It is a reference from The Hitchhiker's Guide to the Galaxy, an
      excellent (personal opinion) science fiction parody. In the story, the mice [they are the smartest beings, in fact, they are the ones who commissioned the creation of Earth] created a supercomputer to tell them the Meaning of Life. After a few million years of calculation (the mice are patient mice), the computer says the answer is 42. When asked, the computer explains that this is the Answer to the Question of Life. To understand it, they must find out the Question of Life. And on the computers direction , the mice create an organic computer named Earth, with all the necessary creature to find the Question. And the rest is history. Read the book, it is quite excellent.
      (5 votes)
  • leaf green style avatar for user Frank
    At , why is 65 not marked as a composite? It's a multiple of 5, isn't it?
    (4 votes)
    Default Khan Academy avatar avatar for user
  • hopper happy style avatar for user :D
    can anyone explain the pattern at ?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • mr pink red style avatar for user Varun
      The pattern at is a visual representation of the Sieve of Erastothenes. 2 and 3 have been checked through the Sieve, and all numbers that are multiples of 2 and 3 have been marked red, eliminating them as possible primes.
      (3 votes)
  • marcimus pink style avatar for user Sejal Rai
    At the sieve states that 65 is a prime number,but it's not possible. Why is it up there?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user Dane Sheridan
    Would the sieve work for smaller squares such as 25, 36, and 4?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • mr pants teal style avatar for user Baba Spickoli
      Yes, if you have a square of 4, the "square" may look like:
      2 3
      4
      You hit 2, and eliminate all multiples of 2, so 4 gets eliminated as it's composite. The "square" would now have the four eliminated and be:
      2 3
      Technically, you don't really need a square, you could set the numbers up as a circle or triangle. I think it just looks nice visually.
      (2 votes)
  • blobby green style avatar for user Nathan
    What is the fastest known, modern method of generating a list of primes such as this?
    (2 votes)
    Default Khan Academy avatar avatar for user

Video transcript

Voiceover: I'm now going to introduce an ancient method for generating a list of primes up to some limit N, called the Sieve of Erathosthenes. Now Erathosthenes was born in 276 BC. So this method was over 2200 years old. But it's very simple and elegant and you can teach it to any child. Now let's say for example we want to calculate all the primes up to 100, this would work in the same way if we wanted to calculate up to 10,000 or a billion. Proceeds as follows, assume all numbers are unmarked, grey is unmarked. We start at the beginning and if we find a number that is unmarked we know it's prime. So we hit two and we say two is primed because it's unmarked. And then the second phase is now we can eliminate all multiples of two because we know their composite. So bam, we jump along and we eliminate all multiples of two, red means composite. And now we repeat. We step along from two to three. Three is unmarked so we mark three as prime. And now we can eliminate all multiples of three. And a really simple optimization is, notice six is already crossed off, we actually cross off the multiples starting at the square of that number. So three times three is nine. We start at nine and mark all multiples of three as composite. And then again we go back, we jump along to four. Well four is marked, we know it's composite. We jump along to five, we find an unmarked number, five is prime. Now five times five 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 seven, we know seven is prime because it's unmarked. Seven times seven is 49, we mark 49 and all multiples of seven above it as composite. Now we move along until we hit 11, 11 is prime. Notice now, 11 times 11 is greater than 100, so we can actually stop at this point. We could have stopped at 10 even, because now all remaining unmarked numbers, if you'll notice, are prime. And in one swoop we can 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 sieve, is if we want to find all the primes up to some number N, we first create a main loop. So we have four all numbers A, from two to the square root of N. So notice here, we stopped when we hit 10, I showed it as 11, we actually stop because we have found all primes. So from two 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 it's composite and that's it. So, you find a number prime, mark of the multiples, go back to the beginning, increment A by one. So we're at two then we go to three then we go to four, five and so on, and when we're done, we have all primes. Notice here that this is also a loop. So we have a main loop for 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 a recording explaining how I set it up.