PrimeSieve.java

public class PrimeSieve {

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

      // initially assume all integers are prime
      final boolean[] isComposite = new boolean[n + 1];


      // mark non-primes <= n using Sieve of Eratosthenes
      for (int i = 2; i*i <= n; i++) {

         // if i is prime, then mark multiples of i as nonprime
         // it suffices to consider mutiples i, i+1, ..., n/i
         if (!isComposite[i]) {
            for (int j = i; i*j <= n; j++) {
               isComposite[i*j] = true;
            }
         }
      }

      // count primes
      int primes = 0;
      for (int i = 2; i<=n; i++) {
         if (!isComposite[i]) primes++;
      }
      System.out.printf ("The number of primes <= %,10d is %,8d%n", n, primes); 
   }
}