This algorithm is attributed to Eratosthenes, a Greek Mathematician who lived around 200 B.C. - I have described the algorithm and how it works:
A non-zero, postive integer (natural number) is prime if it has no other factors other than 1 and itself. 1 is neither prime nor composite. And 2 is the only even-prime number.
So, multiples of 2 cannot be prime (they have 2 as one of their factors) - Similarly, multiples of 3 also cannot be prime. And so on. So, the idea is multiples of a number cannot be prime.
So, let's consider numbers 1 to 100.
Create an array of 100 numbers and set them all to 1.
Let's start from 2 and mark all the multiples of 2 till 100 as non-prime (a.k.a composite). To do this, let's set the value in the array as 0. [The index should go till 100 / 2]
Then, let's start with 3, and again mark all the multiples of 3 till 100 as non-prime.
Next you reach 4. But, this is 0 already. So, the multiples of 4 should already be set to 0. (Since all multiples of 4 are already multiples of 2) - So ignore 4. [And ignore multiples of those numbers which are already marked as 0]. Then start with 5.
So, how far should you go? Some people choose to go till N / 2 (50) - But this is sub-optimal. It is sufficient if we check for all multiples till square root of N. This is because, any factor greater than SQRT(N) should have a partner that is less than SQRT(N) and hence would have already been marked 0. [Please re-read this para-graph :-) if this sounds confusing]
Now iterate through the array and print all indices where the value is non-zero. Voila! You have generated prime-numbers in O(nloglogn).
I wrote an implementation in Python. It was quite cool :o)
#!/usr/bin/env python
# eratosthenes.py
# Sriram V Iyer
#
# Implements the eratosthenes sieve program
# Initialize an array for 100(+1) 1s
# +1 is to accomodate the cases 2 * 50, ...
l = [ 1 for i in range( 100+1) ]
# make the multiples as 0
[ l.__setitem__(i*j, 0) for i in range(2,10) for j in range(2,(100/i)+1) if l[i] != 0 ]
# print indices of the list that are still 1
print [ i for i in range(2,100) if l[i] == 1 ]
I had a discussion with Tejaswi (my Beceem colleague) on an equivalent C code.
Btw, I used the C/C++ compiler feature that initializes unitialized elements of a a partially initialized array to 0. This way, I changed the polarity to 0 -> Prime and 1 -> Composite in the C code. [This way, I needn't write code to initialize the array to 0]
/*
eratos.c
Sieve of Etatosthenes in C/C++
*/
#include "stdio.h"
#include "math.h"
int main()
{
int N = 100, i = 0, j = 0;
int nArray[100+1] = { 0 };
for( i = 2; i < (sqrt((double)N)); i++ ) {
if(nArray[i] == 1) continue;
for( j = 2; j <= (N/i); j += 1 )
nArray[i * j] = 1;
}
for( i = 2; i <>
if(!nArray[i]) printf( "%d ", i );
}
}
There is one more possible optimization - If you can initialize nArray[4] = 1 in the code before the first loop, you can start the inner loop from 3 :-)
PS:- Looks like the "<<" in cout can confuse blogger. So, I rewrote the program without using cout, endl :-)
