primes.java

import java.util.ArrayList;
import java.util.Arrays;

public class Primes {
    public static void main(String[] args) {
        int limit = 1000;

        // Calculate primes under limit and measure the time it took
        long startTime = System.currentTimeMillis();
        ArrayList<Integer> answer = primes(limit);
        long stopTime = System.currentTimeMillis();

        // Calculate duration
        long ms = (stopTime - startTime);

        System.out.println("Found " + answer.size() + " primes in " + ms + "ms");
        System.out.println(answer);
    }

    public static ArrayList<Integer> primes(int limit) {
        ArrayList<Integer> primes = new ArrayList<Integer>();

        // Get an array of booleans which are all set to true
        boolean[] isPrime = new boolean[limit];
        Arrays.fill(isPrime, true);

        // 0 and 1 are not primes, it is easier to cross them off manually than
        // add conditions to the loop
        isPrime[0] = false;
        isPrime[1] = false;

        // Go through all the numbers from 2 up to limit to check if it is a prime
        for (int num = 2; num < limit; num++) {

            // If the boolean of index num is still true when it is reached, it must be a prime
            if (isPrime[num]) {
                primes.add(num);
            } else {
                // By crossing off multiples of primes in the bitmap, all cases
                // are already covered - moving on with composite numbers is
                // unnecessary.
                continue;
            }

            // Cross off all multiples of num as false
            //
            // This is the secret sauce that skips repeating work for the
            // coming numbers, every divisor is taken care of for all numbers
            // only one time.
            //
            // Example: the first loop 2 will be true and added to the primes,
            // then all multiples of 2 (4, 6, 8...limit) will be crossed off in
            // the isPrime bitmap. Since 3 is not a multiple of 2 it will also
            // be added to the primes, but then you get to 4 which has already
            // been determined not to be a prime by the first iteration, and it
            // is skipped.
            for (int multiple = num * 2; multiple < limit; multiple += num) {
                isPrime[multiple] = false;
            }
        }

        return primes;
    }
}