/* Prime Theory #4 - Calculate First N Prime Numbers Keith Fenske Friday, 7 May 2004 Java class name: PrimeTheory4 Copyright (c) 2004 by Keith Fenske. All rights reserved. Calculate the first n prime numbers as efficiently as possible. This program is a modification of PrimeTheory3 that removes many unnecessary steps, such as computing the floating-point square root of each number being tested. PrimeTheory4 is only about four percent faster than PrimeTheory3, which is hardly a significant increase, but the program code is cleaner and makes better use of previous results. Finding the first n prime numbers is a way of measuring the raw sequential speed of a computer. There are no shortcuts or clever formulas in prime number theory. An obvious algorithm tests each number n by dividing n by all numbers from 2 to n-1 and checking for a zero remainder. Once any factor is found (that is, any smaller number that divides evenly without a remainder), there is no need to continue: the number n being tested is not prime. A faster algorithm generates a list of known prime numbers and tests each number n by dividing n by known prime numbers less than or equal to the square root of n. The speed of the first algorithm is characterized by O(n^2) meaning that for large values of n, the computational time is bounded by some constant times the square of n. The speed of the second algorithm (implemented here) is better than O(n^1.5). The size of our list of known prime numbers is limited to approximately the first 5,000,000 primes (a maximum value of 86,028,121), due to the way Java 1.4 allocates memory on Windows 2000. Since we only have to test new numbers for prime factors up to the square root of the test number, our list can be used to test much larger numbers with almost double the number of digits as the largest prime factor in the list (a range of 7,400,837,602,790,641). Note that the frequency of prime numbers slowly decreases as n increases (see following table). The milestone prime numbers are: 1st = 2 10th = 29 100th = 541 1,000th = 7,919 10,000th = 104,729 100,000th = 1,299,709 (1.43 seconds on a Pentium 4 at 2.4 GHz) 1,000,000th = 15,485,863 (33.0 seconds) 10,000,000th = 179,424,673 (14.8 minutes) 100,000,000th = 2,038,074,743 (6.97 hours) 1,000,000,000th = 22,801,763,489 (8.55 days) largest 7-bit prime: 127 (31st) = 0x7F largest 8-bit prime: 251 (54th) = 0xFB largest 15-bit prime: 32,749 (3,512th) = 0x7FED largest 16-bit prime: 65,521 (6,542nd) = 0xFFF1 largest 31-bit prime: 2,147,483,647 (105,097,565th) = 0x7FFFFFFF largest 32-bit prime: 4,294,967,291 (203,280,221st) = 0xFFFFFFFB To obtain the speeds listed above, this program was modified to print only every 10,000th prime number (an arbitrary figure chosen just to show that the program was still running). Otherwise the speeds would be about ten times slower because of formatting the System.out.println calls and waiting for the I/O text to scroll. The formatting is a constant amount of time for each prime number, but the I/O waits introduce delays that are not related to the amount of work being done by the algorithm. When we talk about an efficient algorithm, we don't always mean the fastest program in terms of CPU time. In addition to speed, this program must also satisfy the following conditions: (1) be simple and easy to understand; (2) handle very large numbers; and (3) produce correct results without error. A problem with Big-O notation is revealed when the execution time for this program grows faster than expected for large numbers. Big-O notation assumes that the basic unit of measurement stays constant; for this algorithm, that is the execution time for integer division. Hardware integer division actually takes longer (more machine cycles) for larger integers. Further, even though Java may have 64-bit "long" integers, the underlying computer hardware may not, in which case 64-bit division is emulated with multiple 32-bit division. This program is the property of Keith Fenske. */ public class PrimeTheory4 { /* static class variables (constants) */ static final int MAXFACTORS = 100000; // maximum entries in static final long MAXNUMBER = 999999999L; // maximum number to test static final long MAXPRIMES = 100000L; // maximum number of primes to find public static void main(String[] args) { /* local variables */ long[] factorList; // list of possible prime factors int factorsFound; // highest index used in long factorsTested; // total number of divisions performed int i; // temporary index into long lastPrime; // last prime number found long n; // number we are testing boolean primeFlag; // assume true until a number is not prime long primesFound; // number of prime numbers found int rootIndex; // index of in long rootRange; // the square of long rootValue; // a prime factor greater than or equal to // ... the square root of the number n that // ... is currently being tested /* Initialize our data. This program has no prior knowledge of prime numbers and does not start with a list of the first few known primes. The algorithm is capable of finding all prime numbers without exception. */ factorList = new long[MAXFACTORS + 1]; // vector to hold prime factors factorList[0] = -1; // ignore first element in list factorsFound = 0; // no possible prime factors found yet factorsTested = 0; // no divisions performed yet lastPrime = -1; // no value for last prime number found n = 2; // must start checking with the number two primesFound = 0; // no prime numbers found yet rootIndex = 0; // no prime factors yet, hence no root index rootRange = -1; // no prime factors yet, hence no root range rootValue = -1; // no prime factors yet, hence no root value /* Loop with two limits, so that this program can search either for a given number of prime numbers, or for all prime numbers less than or equal to a given number. */ while ((n <= MAXNUMBER) && (primesFound < MAXPRIMES)) { /* Calculating the square root of each number being tested wastes a lot of time, because we don't need the exact square root in this algorithm. We only need a possible prime factor that is greater than or equal to the square root, and less than the number being tested. */ if (rootRange < n) { /* The old approximate square root is too small. Go to the next higher known prime number. This happens only infrequently as the numbers get bigger. */ if (rootIndex < factorsFound) { rootIndex ++; // index of next known prime number rootValue = factorList[rootIndex]; // save value as approximate root rootRange = rootValue * rootValue; // maximum n that we can test } else if (factorsFound == 0) { /* We're just getting started, so ignore the old square root. */ } else { System.out.println( "Search ends early.\nPrime factor list is limited to " + rootIndex + " entries (value " + rootValue + ", range " + rootRange + "),\n which is too small to test the number " + n + "."); break; // exit from while loop } } /* Use the list of possible prime factors to determine if the new number is prime. This very quickly eliminates even numbers, multiples of three, etc, so special processing is not required to avoid testing those numbers in the first place. */ primeFlag = true; // assume number is prime // System.out.print("testing n = " + n + " with"); // trace for debugging for (i = 1; i <= rootIndex; i ++) { factorsTested ++; // one more division performed // System.out.print(" " + factorList[i]); // append to "testing/with" if ((n % factorList[i]) == 0) { primeFlag = false; // number is not prime: found a divisor break; // exit from for loop } } // System.out.println(" " + primeFlag); // finish the "testing/with" phrase /* If the number is prime, then add it to our list of known primes. */ if (primeFlag) // is the number n prime? { lastPrime = n; // yes, remember last prime number found primesFound ++; // increment number of prime numbers found if (primesFound <= MAXFACTORS) // any more room in the factor list? { factorsFound = (int) primesFound; // yes, new size of factor list factorList[factorsFound] = n; // and save prime factor in list } // if ((primesFound % 10000) == 0) // limit printing on large searches System.out.println("Prime number " + primesFound + " is " + n + "."); } /* We have finished testing this number. Get the next number. */ n ++; // next number to check } /* Print a summary. This mostly makes sense to the programmer. */ System.out.println("Program ends with primesFound = " + primesFound + " (value " + lastPrime + "),\n factorsFound = " + factorsFound + " (value " + factorList[factorsFound] + ", range " + (factorList[factorsFound] * factorList[factorsFound]) + "),\n rootIndex = " + rootIndex + " (value " + rootValue + ", range " + rootRange + ")."); System.out.println("Average number being tested was divided by " + (Math.round(100.0 * factorsTested / (n - 2)) / 100.0) + " possible prime factors."); System.out.println("Effective use of prime factor list (size " + MAXFACTORS + ") was " + (Math.ceil(10000.0 * rootIndex / MAXFACTORS) / 100.0) + " percent."); } // end of main() method } // end of PrimeTheory4 class /* Copyright (c) 2004 by Keith Fenske. All rights reserved. */