Simon Buckle's Weblog

Here’s a problem that you some times come across in problem sets and job interviews:  

Q. Write a program to generate all the prime numbers up to N.

The simplest algorithm I can think of is the Sieve of Eratosthenes.
Here’s my attempt:

public class PrimeSieve {

     public static void main(String[] args) {
	int N = Integer.parseInt(args[0]);

	boolean[] isPrime = new boolean[N+1];
	Arrays.fill(isPrime, true);

	int max = (int)Math.sqrt(N);

	for (int i=2; i<=max; i++) {
	   if (isPrime[i]) {
	      // Remove all of the multiples of i
	      for (int j=2; i*j<=N; j++) {
		 isPrime[i*j] = false;
	      }
	    }
	}

	// List the primes
	for (int k=2; k<=N; k++) {
	    if (isPrime[k]) System.out.print(k+" ");
	}
     }
}

That's all. You can leave now.