1. Algorithm Description

Sieve of Eratosthenes is an ancient algorithm in mathematics that allows us to find all prime numbers up to a specific integer value . It works well on small inputs (the maximum value of the interval is 10.000.000 – 20.000.000 ) .

I am not going to enter into too many details, as the algorithm itself is not very complicated and there are plenty resources on the web describing the concept of a sieve in general and the Eratosthenes Sieve in particular . Still I will implement this algorithm, for the sake of having a “complete” (far from the truth) reference on algorithms and data-structures .

The algorithm is based on the following technique:

1. Create an array S of integers with size N (the maximum value of the interval). Mark all positions in the array as possible primes .
2. Start iterating the array from position 2 (the first prime number), and mark every multiple of 2 as non-prime: S[2*2], S[2*3], …
3. Find the next non-prime number (that wasn’t previously marked), in our case 3, and continue to mark as non-prime all its multiples: S[3*2], S[3*3], …
4. Find the next non-prime number (that wasn’t previously marked), in our case 5, and continue to mark as non-prime all its multiples: S[5*2], S[5*3], …
5. Repeat the logic, and stop when the next non-prime number, k, satisfies the following relationship k*k > p .

Sieve of Eratosthenes pseudo-code:

2. Algorithm Implementation

2.1 Implementation in C

The C-implementation is pretty straight-forward . Instead of while loops, for simplicity I will prefer for loops . The following program will print all the prime numbers between [0..10.000] .

And the output is (unfold):

Leave a reply

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url=""> 

required

Are we human, or are we dancer *