Sieving Numbers

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.

Leave a Reply