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:

  1. Start looping i from 2 to the square root of N
  2. 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)
  3. Skip over values that have already been removed
  4. 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.

Leave a Reply

 

Staypressed theme by Themocracy