// This program lists the prime numbers in a range using Sieve of Eratosthenes
// Reference: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
public class SieveOfEratosthenes {

  private boolean isPrime[]; // never use the 0th and 1st elements

  // Constructor. N is the upper range boundary
  public SieveOfEratosthenes(int N){
    isPrime = new boolean[N];
    for(int i=2; i<isPrime.length; i++) isPrime[i]=true;
    markPrime();
  }

  // Mark the prime numbers using Sieve of Eratosthenes
  // To be called by constructor only.
  private void markPrime(){
    for(int i=2; i<isPrime.length; i++)
      if(isPrime[i])
        for(int j=i+i; j<isPrime.length; j+=i) isPrime[j] = false;
  }

  // Print all the prime numbers in the array. Assumed marked.
  public void printPrime(){
    // isPrime[0] and isPrime[1] are ignored though both are initialized to true.
    for(int i=2; i<isPrime.length; i++)
      if(isPrime[i]) System.out.println(i);
  }

  public static void main( String args[] ){
    SieveOfEratosthenes s = new SieveOfEratosthenes(10000);
    s.printPrime();
  }
}