*Sift the twos and sift the threes:**The Sieve of Eratosthenes.**When the multiples sublime,**The numbers that remain are prime.*

- http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
- "The Genuine Sieve of Eratosthenes," Melissa E. O’Neill: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf (PDF)
- http://www.utm.edu/research/primes/prove/prove2_1.html
- http://www.fpx.de/fp/Software/Sieve.html

- QuadraticSieve? for factorization: http://planetmath.org/encyclopedia/QuadraticSieve.html
- StanislawUlam?'s "LuckyNumbers?": http://www.maa.org/mathland/mathtrek1.html
- Sieving to produce lists of squares, cubes, etc.: http://go.hrw.com/resources/go_mt/a1/c8/ASIEVES.PDF (PDF)

There is a lot of confusion about this problem. It is *not* about finding any old algorithm to find a series of primes; SieveOfEratosthenes is a very *specific* algorithm for finding all the prime numbers up to a given number,

- On paper,
*write*the numbers 2...n -
*Circle*the first number, 2. Call it**P** -
*Strike out*all the**P**'s multiples (for 2 it's 4, 6, 8, ...)*by counting up*from**P**in increments of**P** -
*Circle*the smallest number not yet struck out. Call it**P**, and*repeat*from the previous step - When there's no more numbers to circle,
*stop*. You've now circled all the prime numbers up to**n**

int main(int argc, char **argv) { int top_value = 100; int count = top_value - 1; int *array = calloc( top_value + 1, sizeof(int)); int i, prime, multiple; /* mark each int as potentially prime */ for (i=2; i <= top_value; ++i) array[i] = 1; /* for each starting prime, mark its every multiple as non-prime */ for (prime = 2; prime <= top_value; ++prime) { if (array[prime]) for (multiple = 2*prime; multiple <= top_value; multiple += prime) if (array[multiple]) { array[multiple] = 0; --count; } } /* Now that we have marked all multiples of primes as non-prime, print */ /* the remaining numbers that fell through the sieve, and are thus prime */ for (i=2; i <= top_value; ++i) { if (array[i]) printf("%d ", i); } printf("\n\n %d primes up to %d found.\n", count, top_value); exit(0); }-- DougMerritt (

A comment, prompted by the SieveOfEratosthenesInManyProgrammingLanguages page ... Some of the implementations over there use this algorithm:

- Get a list of all integers (possibly implicit, possibly delayed)
- For as long as necessary
- Remember the first element,
**P** - Print
**P**- it's prime - Remove
**P**from the front - For each remaining element
- Compute
*(n mod P)*, and if the result is 0 ...- Remove it from the list

- Compute

- Remember the first element,

If the above explanation is clear to you then you don't need to read any further. However, for the sake of being concrete here are two PythonLanguage scripts to illustrate the point. They are not intended to be idiomatic Python, they are not intended to be general. They are for teaching about the algorithm, not about Python. Feel free to improve them, but please, keep in mind the purpose.

candidates = range(2,n+1) limit = int(sqrt(n)) prime = candidates[0] result = [] while prime<=limit: result += [prime] c0 = [] for i in candidates: if 0 != i%prime: c0.append(i) candidates = c0 prime = candidates[0] result += candidatesNotice how elements are actually removed from the list of candidates, and explicit divisions are performed to see which remaining candidates should be kept. This is

def sieve(n): candidates = range(n+1) fin = int(n**0.5) for i in xrange(2, fin+1): if not candidates[i]: continue candidates[2*i::i] = [None] * (n//i - 1) return [i for i in candidates[2:] if i] sieve(19) # returns [2, 3, 5, 7, 11, 13, 17, 19]

See also SieveOfEratosthenesInManyProgrammingLanguages

CategoryMath

View edit of January 24, 2013 or FindPage with title or text search