Main content

## Computer science theory

### Course: Computer science theory > Unit 2

Lesson 6: Primality test- Introduction
- Primality test challenge
- Trial division
- What is computer memory?
- Algorithmic efficiency
- Level 3: Challenge
- Sieve of Eratosthenes
- Level 4: Sieve of Eratosthenes
- Primality test with sieve
- Level 5: Trial division using sieve
- The prime number theorem
- Prime density spiral
- Prime Gaps
- Time space tradeoff
- Summary (what's next?)

© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# Sieve of Eratosthenes

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

## Want to join the conversation?

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

- This may be a silly question, can a negative number be prime? For example, -3,-5,-7 etc(15 votes)
- By definition a prime number is

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

So negative numbers cannot be prime numbers.(26 votes)

- 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?(5 votes)
- 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.(19 votes)

- Why do we want to know if one or more numbers are prime?(6 votes)
- 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)

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

- At3:27, why is 65 not marked as a composite? It's a multiple of 5, isn't it?(4 votes)
- Probably just a "typo" kind of error. I don't think he's actually using the program at that point.(3 votes)

- can anyone explain the pattern at1:32?(2 votes)
- The pattern at1:32is 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)

- At2:53the sieve states that 65 is a prime number,but it's not possible. Why is it up there?(2 votes)
- I think he just miscolored it when he redrew it.(2 votes)

- Would the sieve work for smaller squares such as 25, 36, and 4?(2 votes)
- 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)

- What is the fastest known, modern method of generating a list of primes such as this?(2 votes)
- For finding all the primes up to n, the Sieve of Erastothenes, and the Sieve of Atkin are, for practical purposes, the fastest.

In theory (based on time complexity), the Sieve of Atkin is the fastest of the two:

https://en.wikipedia.org/wiki/Sieve_of_Atkin

However, in practice, depending on the implementation, the Sieve of Erastosthenes may be faster.(1 vote)

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