Java implementation of the Sieve of Eratosthenes, an algorithm to calculate prime numbers.

PrimesSieve.java

/**
 * Implementation of the sieve of Eratosthenes for finding all the primes up to
 * a given number (MAX in this case).
 * From the command line:
 *   Step 1 (compile): javac PrimesSieve.java
 *   Step 2 (run):     java PrimesSieve
 */
public class PrimesSieve {
  public static void main(String[] args) {
    final int MAX = 1_000_000;
    // Create an array of boolean values indicating whether a number is prime.
    // Start by assuming all numbers are prime by setting them to true. 
    boolean[] primes = new boolean[MAX];
    for (int i=0; i<primes.length; i++) {
      primes[i] = true;
    }

    // Loop through a portion of the array (up to the square root of MAX). If
    // it's a prime, ensure all multiples of it are set to false, as they
    // clearly cannot be prime.
    for (int i=2; i<Math.sqrt(MAX)+1; i++) {
      if (primes[i-1]) {
        for (int j=(int) Math.pow(i,2); j<=MAX; j+=i) {
          primes[j - 1] = false;
        }
      }
    }

    // Output the results
    int count = 0;
    for (int i = 2; i < MAX; i++) {
      if (primes[i - 1]) {
        System.out.println(i);
        count++;
      }
    }
    System.out.printf("There were %d primes up to %d", count, MAX);
  }
}