// copyright Code Complete, p.779

public class PrimeSieve {

  public static void main(String[] args) {

    int max = Integer.parseInt(args[0]);
    boolean[] isPrime = new boolean[max];

    for (int primeCandidate = 2; primeCandidate < max; primeCandidate++) {
      isPrime[ primeCandidate ] = true;
    }

    for (int factor = 2; factor < max/2; factor++) {
      int factorableNumber = factor + factor;
      while ( factorableNumber < max ) {
	isPrime[ factorableNumber ] = false;
	factorableNumber += factor;
      }
    }

    for (int primeCandidate = 0; primeCandidate < max; primeCandidate++) {
      if ( isPrime[ primeCandidate ]) {
	System.out.println( primeCandidate + " is prime.");
      }
    }
  }

}