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");

}

## 2 comments:

Er..I hate to be stickler..but have you actually run this code ?

That's a mighty weird for-loop (no termination condition ??? ) and some of those brackets REALLY don't match..

It's not a bad idea to run your code before you post it

Yea, it looks like Blogger removed some items. But I have run it in my code and it was fine. (Maybe except that it also print "1", which I hear is technically not a prime number?).

Post a Comment