PrimeSieve.java

/*************************************************************************
 *  Compilation:  javac PrimeSieve.java
 *  Execution:    java -Xmx900MB -Xms900MB PrimeSieve N
 *  
 *  Computes the number of primes less than or equal to N using
 *  the Sieve of Eratosthenes.
 *
 *  The 900MB is the amount of memory you want to allocate to the
 *  program. If your computer has less, make this number smaller,
 *  but it may prevent you from solving the problem for very large
 *  values of N.
 *
 *                  N     Primes <= N
 *  ---------------------------------
 *                 10               4   
 *                100              25  
 *              1,000             168  
 *             10,000           1,229  
 *            100,000           9,592  
 *          1,000,000          78,498  
 *         10,000,000         664,579  
 *        100,000,000       5,761,455  
 *      1,000,000,000      50,847,534  
 *     10,000,000,000     455,052,511  
 *    100,000,000,000   4,118,054,813  
 *  1,000,000,000,000  37,607,912,018  
 * 10,000,000,000,000 346,065,536,839  
 *
 *************************************************************************/


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

        // initially assume all integers are prime
        boolean[] isPrime = new boolean[N + 1];
        for (int i = 2; i <= N; i++)
            isPrime[i] = true;

        // 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
            if (isPrime[i]) {
                for (int j = i; i * j <= N; j++)
                    isPrime[i*j] = false;
            }
        }

        // count primes
        int primes = 0;
        for (int i = 2; i <= N; i++)
            if (isPrime[i]) primes++;
        System.out.println("The number of primes <= " + N + " is " + primes);
    }
}