## Prime numbers, fast

A co-worker of mine and I were having a discussion about prime numbers and how to calculate them. I clearly recall that very early in my Computer Science schooling that I was given a “Find all the prime numbers between 1 and *N*” programming assignment.

I admit that from a first-year perspective that I attacked that assignment with brute force. I thought the best way to find those primes was to write an “isPrime(int x)” function and loop from 1 through *N* checking each one. In my mind I was certain that the way to check if a value was prime was to start by performing modulus on it ** N % (N/2)** and inner-loop my way down to

**2**to check if the value was divisible by another number.

WRONG! There is another way to find all the primes from 1 to *N* and it is this:

- Start looping
**i**from 2 to the square root of*N* - For every value of
**i**remove every multiple of**i**there-after (meaning that a value of**2**ensures that every**even**number is removed from the list of prime numbers,**3**then removes every value divisible by**3**, etc) - Skip over values that have already been removed
- When
**i**has reached the square root of N then you are left with**only**the prime numbers between 1 and*N*

Here is a benchmark of just how quick (using C) the prime numbers between 1 and 2 million can be found. Note, by default my program prints every value to terminal so I piped it into a file (which I can open and evaluate for proof that only prime values are left).

time ./FindPrime 2000000 > dat.dat

real 0m0.142s

user 0m0.136s

sys 0m0.008s

The method described is called the **Sieve of Eratosthenes**. Here is my source code for the exercise. Happy programming.