    001    package calhoun.util;
    002
    003
    004    public class PrimeUtil {
    005            /** The first prime number */
    006            static int INITIAL_SIZE = 1000;
    007
    008            static long maxPrime = -1;
    009            public static int[] primes;
    010
    011            /** Returns an array of primes that includes all primes up to at least N.  May contain more. */
    012            public static int[] primesToAtLeastN(int number) {
    013                    if(maxPrime < number) {
    014                            primes = primesLessThan(number);
    015                            maxPrime = number;
    016                    }
    017                    return primes;
    018            }
    019
    020            /*
    021             * Compute prime numbers, after Knuth, Vol 1, Sec 1.3.2, Alg. "P".
    022             * Note that there may be more efficient algorithms for
    023             * finding primes.
    024             */
    025            private static int[] primesLessThan(long stop) {
    026                    int[] prime = new int[INITIAL_SIZE];
    027
    028                    prime[0] = 1; // P1 (ignore prime[0])
    029                    prime[1] = 2; // P1 (ignore prime[0])
    030                    int n = 3; // odd candidates
    031                    int j = 1; // numberFound
    032
    033                    boolean isPrime = true; // for 3
    034                    boolean doMore = true;
    035                    do {
    036                            if (isPrime) {
    037                                    if (j == INITIAL_SIZE - 1) {
    038                                            // Grow array dynamically if needed
    039                                            int[] np = new int[INITIAL_SIZE * 2];
    040                                            System.arraycopy(prime, 0, np, 0, INITIAL_SIZE);
    041                                            INITIAL_SIZE *= 2;
    042                                            prime = np;
    043                                    }
    044                                    prime[++j] = n; // P2
    045                                    isPrime = false;
    046                                    if(n > stop)
    047                                            doMore = false;
    048                            }
    049                            n += 2; // P4
    050
    051                            for (int k = 2; k <= j && k < INITIAL_SIZE; k++) { // P5, P6, P8
    052                                    long q = n / prime[k];
    053                                    long r = n % prime[k];
    054                                    if (r == 0) {
    055                                            break;
    056                                    }
    057                                    if (q <= prime[k]) { // P7
    058                                            isPrime = true;
    059                                            break;
    060                                    }
    061                            }
    062                    } while (doMore); // P3
    063                    return prime;
    064            }
    065    }