Prime Numbers

package prime;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;

/**
 * A prime number utility for generating X number of primes, determining whether
 * a given number is prime, and computing the prime factorization for a number.
 *
 * For determining whether a number N is prime, you only need to know all the
 * primes up to and including sqrt(N).
 *
 * @author Philip Diffenderfer
 *
 */
public class Prime
{

    public static void main( String[] args )
    {
        Prime p = new Prime( 10000000 );

        // Load 100,000 primes into cache
        long t0 = System.nanoTime();
        p.initialize( 10000000 );

        System.out.println( ( System.nanoTime() - t0 ) * 0.000000001 + " seconds to initialize " + (p.length + 1) + " primes" );

        // Last Prime
        System.out.println( p.primes[p.length] );

        // Prime Factors
        System.out.println( p.factorize( 83475L, new ArrayList<Long>() ) );
    }

    // The cache of prime numbers
    private long[] primes;

    // The index of the last prime number in the cache
    private int length;

    /**
     * Instantiates a new Prime class with a maximum number of primes it can
     * generate.
     *
     * @param primeCountMax
     *            The maximum number of primes this class may be able to store.
     */
    public Prime( int primeCountMax )
    {
        primes = new long[primeCountMax];
        primes[0] = 2;
        primes[1] = 3;
        primes[2] = 5;
        length = 2;
    }

    /**
     * Prints out all primes in the prime cache one line at a time into the
     * PrintStream.
     *
     * @param out
     *            The PrintStream to print the prime cache out to.
     */
    public void print( PrintStream out )
    {
        for (int i = 0; i <= length; i++)
        {
            out.println( primes[i] );
        }
    }

    /**
     * Determines whether the given number is prime.
     *
     * @param n
     *            The number to check for primeness.
     * @return True if the number is prime, otherwise false.
     */
    public boolean isPrime( long n )
    {
        // Does n exist in the prime cache?
        if ( isQuickPrimeApplicable( n ) )
        {
            // Perform a quick search for n.
            return isQuickPrime( n );
        }

        long max = (long) Math.sqrt( n );

        // Ensure we have enough primes in the prime cache to determine whether
        // or not n is a prime.
        fillPrimes( max );

        // If itself is it's only factor, it's a prime.
        return getFactor( n, max ) == n;
    }

    /**
     * Returns the first prime factor for n, or n if n is prime.
     *
     * @param n
     *            The number to find the first prime factor of.
     * @param nsqrt
     *            The square-root of n.
     * @return The first prime factor of n, or n if it's prime.
     */
    private long getFactor( long n, long nsqrt )
    {
        for (int i = 0; i <= length; i++)
        {
            long p = primes[i];

            if ( p > nsqrt )
            {
                return n;
            }

            if ( n % p == 0 )
            {
                return p;
            }
        }

        return n;
    }

    /**
     * Ensures the prime cache has all primes up to some number max.
     *
     * @param max
     *            The number the prime cache should encompass (have primes <=)
     */
    public void fillPrimes( long max )
    {
        while ( primes[length] < max )
        {
            long p = nextPrime( length );

            primes[++length] = p;
        }
    }

    /**
     * Ensures the prime cache has at least primeCount primes.
     *
     * @param primeCount
     *            The minimum number of primes the prime cache should have.
     */
    public void initialize( int primeCount )
    {
        --primeCount;

        while ( length < primeCount )
        {
            long p = nextPrime( length );

            primes[++length] = p;
        }
    }

    /**
     * Computes the next prime in the sequence of all primes based on the prime
     * at the given index in the prime cache.
     *
     * @param n
     *            The index of a prime in the prime cache, the prime this method
     *            returns will be the next prime in the sequence.
     * @return The next prime in the sequence of primes.
     */
    public long nextPrime( int n )
    {
        long x = primes[n] + jump( n );

        while ( getFactor( x, (long) Math.sqrt( x ) ) != x )
        {
            x += jump( ++n );
        }

        return x;
    }

    /**
     * A number is a quick prime if it exists in the currently generated cache
     * of primes. This can efficiently be determined with a binary search.
     *
     * @param n
     *            The prime to check.
     * @return True if the given number exists in the prime cache.
     */
    public boolean isQuickPrime( long n )
    {
        return Arrays.binarySearch( primes, 0, length + 1, n ) >= 0;
    }

    /**
     * A number is quick prime applicable if there exists a prime in the cache
     * that is larger than the provided number. This implies a search can be
     * done in the array to determine if the provided number is a prime.
     *
     * @param n
     *            The number to check for quick prime applicability.
     * @return True if the number exists on the prime cache, otherwise false.
     */
    public boolean isQuickPrimeApplicable( long n )
    {
        return n <= primes[length];
    }

    /**
     * Given the index of a prime, return the jump (either 2 or 4) to use to
     * approximate the next prime. The first 3 primes are excluded from this
     * rule.
     *
     * @param x
     *            The index of the prime.
     * @return The amount to jump to the next possible prime.
     */
    private int jump( int x )
    {
        return ( 1 << ( ( x & 1 ) + 1 ) );
    }

    /**
     * Adds all prime factors of n to the given collection of numbers.
     *
     * @param n
     *            The number to find all prime factors of.
     * @param primeFactors
     *            The collection to add prime factors to.
     * @return The collection given.
     */
    public <D extends Collection<Long>> D factorize( long n, D primeFactors )
    {
        if ( isQuickPrimeApplicable( n ) && isQuickPrime( n ) )
        {
            return primeFactors;
        }

        long max = (long) Math.sqrt( n );

        fillPrimes( max );

        while ( n != 1 )
        {
            long f = getFactor( n, max );

            primeFactors.add( f );

            n /= f;

            max = (long) Math.sqrt( n );
        }

        return primeFactors;
    }

}