Sieve of Eratosthenes (finding all prime numbers up to a specific integer)

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:

FUNCTION SIEVE(max)
  sieve := ARRAY[2..max]
  FOR elem IN sieve
    elem := PRIME
  i := 2
  WHILE i * i < max DO
    IF sieve[i] = PRIME THEN
      j := 2
      WHILE j * i < max DO
        sieve[i * j] := NON-PRIME
          j := j + 1
    i := i + 1
  RETURN sieve

2. Algorithm Implementation

Euclid’s Algorithm

Recently I’ve started to implement (or reimplement) the most common algorithms a software developer should know . One of the nicest books I found on this topic is Algorithms in C (Robert Sedgewick) . Of course, there is this and this, but lately I am more interested on the “implementation” side of things than on maths and theory .

1. Algorithm Description

Euclid’s Algorithm is an efficient method for calculating the greatest common divisor of two numbers (aka GCD) . The  GCD of two numbers is considered the largest number that divides both of them (without leaving a reminder) .

Euclid’s algorithm is based on the principle that given two numbers a and b, if a is greater than b than the greatest common divisor of a and b is the same with the common divisor of b and (b – a) . If we transform the above property into “code” (actually pseudo-code) the algorithm looks like this:

FUNCTION GCD(num1, num2)
  WHILE num1 > 0
    IF num1 < num2
      SWAP (num1, num2)
    num1 := num1 - num2
  RETURN num2

The above pseudo-code is called the subtraction-variant . We can of course replace the repetitive subtractions with one division . The division-based version looks like this (in pseudo-code):

FUNCTION GCD(num1, num2)
  WHILE num1 > 0
    tmp  := num1
    num1 := num2 MOD num1
    num2 := tmp
  RETURN num2

There is also a recursive version of the algorithm:

FUNCTION GCD(num1, num2)
  IF num1 <> 0 THEN
    RETURN GCD(num2 MOD num1, num1)
  RETURN num2