Computer science theory
- 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?)
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)
- 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)
- 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:
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:
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:
However, in practice, depending on the implementation, the Sieve of Erastosthenes may be faster.(1 vote)