Friday, November 09, 2007

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for determining prime numbers less than a given maximum number. Prime numbers have become suddenly important to me, especially in scenarios where events must not collide. In that case, staggering timeouts minimizes the chances when primes are used.
This is the Java implementation of the algorithm, the quick and dirty way. Of course there's more complex and efficient algorithms out there. This one is good enough for small maximums and runs in O(n lg n) time. Beyond a certain number, the system will run out of memory and begin taking longer to determine the next prime.:
/**
* Prints a list of prime numbers less than the max given.
* @param max Prime numbers will be less than this maximum.
*/
private static void printPrimes(int max) {
// Create max-sized array
boolean[] a = new boolean[max];
// Initially assume all numbers are not non-prime
for (int i = 2; i+=1)
a[i] = true;
}
// Sieve of Eratosthenes algorithm
for (int i = 2; i+=1)

if (a[i] != false) {
for (int j = i; j * i < max; j+=1)
a[i * j] = false;
}
}
}
// Print the primes, 0 and 1 are not
for (int i = 2; i+=1)
if (a[i]) {
System.out.print(" " + i);
}
}
System.out.print("\n");
}