# Sieve

Published: Tue 01 August 2017

In Blog.

A prime number is a number greater that one which can be evenly divided only by one and itself. For instance, we can divide 3 by 2 and we’d get 1.5, but that wouldn’t be even. We can divide 3 by 3 and get 1; that’s an even division (even though the answer is odd), and we can divide 3 by 1 and get 3—that’s also an even division. Three, then, is an example of a prime number.

## Are primes odd?

Some odd numbers are prime, but not all odd numbers are prime, although we can say with a good level of confidence that almost all prime numbers are odd (the exception being 2, of course).

The assertion “almost all primes are odd” is a little odd, because primes aren’t really odd, they’re sort-of beautiful. That's probably one of the reasons why mathematicians give them so much attention.

## Eratosthenes

The Sieve of Eratosthenes (pronunciation here for those to-which this is Greek) is an algorithm for finding prime numbers. I make no claim to be in any way prime-number-generation literate, so, as a disclaimer, this is the only way I know of to find primes short of an ugly brute-force approach.

In short, it goes like this:

1. Choose a number n up-to-which you wish to find all prime numbers;

2. Iterate through the numbers 2 to √n for each value (i):

2.1 Starting at the square of the value (i × i), “cross off” values by repeatedly doing an i-sized “hop” to the subsequent value, until i is greater than the square-root of n (√n);

For example, this C# snippet demonstrates the algorithm for a small n:

```var upTo = 31;
var numbers = Enumerable.Range(2, upTo-1).ToList();
var end = (int)Math.Sqrt(upTo);
for (int i=2; i < end; i++) {
for (int j=i*i; j <= upTo; j+=i) {
numbers.Remove(j);
}
}

foreach (var p in numbers)
Console.WriteLine(p);
```
``` s  m  t  w  t  f  s

2  3     5
7          11
13          17    19
23
29    31
```