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. This class caches primes to very quickly check whether a number is a prime.

Prime.java

public class Prime
{

    /* BEGIN TEST */
	public static void main( String[] args )
	{
		Prime p = new Prime( 100000 );

		// Load 100,000 primes into cache
		long t0 = System.nanoTime();
		p.initialize( 100000 );
		
		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>() ) );
		
		// 100 primes
		p.print( System.out, 100 );
	}
	/* END TEST */
	

	// 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, int n )
	{
		for (int i = 0; i <= n; 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] + 2;

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

		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];
	}

	/**
	 * 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;
	}

}