John Ousterhout prime generatror

PrimeGenerator2.java

package literatePrimes;

import java.util.ArrayList;

public class PrimeGenerator2 {

    /**
     * Computes the first prime numbers; the return value contains the
     * computed primes, in increasing order of size.
     * @param n
     *      How many prime numbers to compute.
     */
    public static int[] generate(int n) {
        int[] primes = new int[n];

        // Used to test efficiently (without division) whether a candidate
        // is a multiple of a previously-encountered prime number. Each entry
        // here contains an odd multiple of the corresponding entry in
        // primes. Entries increase monotonically.
        int[] multiples = new int[n];

        // Index of the last value in multiples that we need to consider
        // when testing candidates (all elements after this are greater
        // than our current candidate, so they don't need to be considered).
        int lastMultiple = 0;

        // Number of valid entries in primes.
        int primesFound = 1;

        primes[0] = 2;
        multiples[0] = 4;

        // Each iteration through this loop considers one candidate; skip
        // the even numbers, since they can't be prime.
        candidates: for (int candidate = 3; primesFound < n; candidate += 2) {
            if (candidate >= multiples[lastMultiple]) {
                lastMultiple++;
            }

            // Each iteration of this loop tests the candidate against one
            // potential prime factor. Skip the first factor (2) since we
            // only consider odd candidates.
            for (int i = 1; i <= lastMultiple; i++) {
                while (multiples[i] < candidate) {
                    multiples[i] += 2*primes[i];
                }
                if (multiples[i] == candidate) {
                    continue candidates;
                }
            }
            primes[primesFound] = candidate;

            // Start with the prime's square here, rather than 3x the prime.
            // This saves time and is safe because all of the intervening
            // multiples will be detected by smaller prime numbers. As an
            // example, consider the prime 7: the value in multiples will
            // start at 49; 21 will be ruled out as a multiple of 3, and
            // 35 will be ruled out as a multiple of 5, so 49 is the first
            // multiple that won't be ruled out by a smaller prime.
            multiples[primesFound] = candidate*candidate;
            primesFound++;
        }
        return primes;
    }
}