The Curmudgeon Coder Rants and raves, tips and tricks from Aaron Korver, the curmudgeon coder

Prime Number Fun

Today we shall visit the subject of prime numbers. Yup, Math.

So first the definition of a prime number is a number such that it is only evenly divisable by itself and 1. But you already knew that right?

To test if the number n is prime, you can use the following algorithm which takes use of the modulus operator:

for (int i=2; i < n; i++){

   if (n%i==0){ return false; }

}

return true;

Alas, we have to loop through every single number up to n-1 starting at 2, so it will be n-2 iterations. We can do a little bit of work and make this a bit better. First of all, if a number is divisible by another number, say x, then there will be one more number, say y, that it is also divisable. Such that n/x = y and n/y = x. There is a kind of reflection that happens along the number line. It can be observed that this reflection's pivot is at the sqare root of n. So our first improvement would only be to iterate up to the sqrt(n). Secondly, if the number is odd, we can safely start at 3 and jump up every two numbers from there. So only check 3, 5, 7, etc... This will also reduce the number of iterations that are necessary.

Okay, so here is our enhanced algorithm. Note I make no claims on if it performs better than the other as I haven't benchmarked it. I can only show that the number of iterations will be less.

public boolean isPrime (int n){

   if (n<=1) return false;

   if (n==2) return true;

   if (n%2==0) return false;

   int m=Math.sqrt(n);

   for (int i=3; i<=m; i+=2){

      if (n%i==0){

         return false;}

   }

   return true;}

Now then, what if we want to examine a set of numbers and pull out all the primes in a set? Well, one way to do that would be to loop through each number and determine if it is prime or not. That algorithm is below:

public int[] findPrimes(int set[]){

    int[] returnInts = new int [set.size];

    int index = 0;

    for(int x = 0; x <= set.size; x++){

         if(isPrime(set[x]))

             {returnInts[index++] = set[x];}

    }

    return returnInts;}

Unfortunately that means we have to loop first through the set, and then loop from 3 to qrt(n) on each of the numbers in the set. That is a lot of looping. Insead we can use what is knows as The Sieve of Eratosthenes.

See the wikipeda entry for how it works exactly, but basically, we start with the set and remove all numbers which are a multiple of 2 (but not 2, since 2 is prime). Then remove all numbers which are a multiple of 3, then of 4, etc up to the square root of the largest value in the set. Below is the algorithm for this.

// n here is the largest value in the set and we are assuming all the numbers from 1 to n. But we can easily modify this // to be operated on a given set. This algorithm returns an array of booleans which represent if the number is prime or not.

public boolean[] sieve(int n){

   boolean[] prime=new boolean[n+1];

   Arrays.fill(prime,true);

   prime[0]=false;

   prime[1]=false;

   int m=Math.sqrt(n);

   for (int i=2; i<=m; i++)

      if (prime[i])

         for (int k=i*i; k<=n; k+=i)

            prime[k]=false;

   return prime;} 

Posted at 11:22PM Jun 25, 2006 by Aaron in General  |