## 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
```