The sieve of Eratosthenes !!

The ancient Greek mathematician Eratosthenes suggested the following algorithm for finding all primes that not exceeding a given number n. Let us take an array S of length n and fill it with figures one (mark them as uncrossed). Now we will consistently see the elements of S [k], starting with k = 2. If S [k] = 1, then fill in with zeros (cross out or sow) all subsequent table cells, which numbers are multiple of k. As result is an array in which cells contain 1 if and only if the number of cell is a prime number.

A lot of time could be saved by noting that a composite number is less than n, at least one of the divisors does not exceed , the sowing process sufficiently to finish on . This is the Sieve of Eratosthenes animation, taken from Wikipedia

Click on the image to get an idea of what is happening. The animation says it all.

S = [];
S[1] = 0; // 1- not a prime number
/ / fill it with figures one
for(k=2; k<=n; k++)
S[k]=1;

for(k=2; k*k<=n; k++){
/ / if k is a simple (not crossed out)
if(S[k]==1){
/ / then we cross out multiples of k
for(l=k*k; l<=n; l+=k){
S[l]=0;
}
}
}
return S;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s