15.6 Generating Prime Numbers

   

 
Java Number Cruncher: The Java Programmer's Guide to Numerical Computing
By Ronald  Mak

Table of Contents
Chapter  15.   Prime Numbers

15.6 Generating Prime Numbers

Now that we have a way to test a number for primality , we can also ask, Are there formulas that generate prime numbers? There are such formulas, but mathematicians have yet to find a formula that generates only prime numbers.

A well-known formula for primes is the one that generates the so-called Mersenne primes, [8]

[8] Marin Mersenne (1588 C1648) was a French monk who taught philosophy and investigated prime numbers. He first published his formula in 1644.

graphics/15equ06.gif


where p itself is prime. For example, M 2 = 3, M 3 = 7, M 5 = 31, M 7 = 127 are all prime, but M 11 = 2047 is composite its factors are 23 and 89. Computer scientists continue to vie for the honor of being the discoverer of the largest known Mersenne prime. As of late 2001, the largest one found is M 13,466,917 with 4,053,946 digits.

A number of integer-valued quadratic polynomials of the form

graphics/15equ07.gif


where a, b, and c are integer constants, generates prime numbers for a limited domain of integer values for the variable n. Perhaps the most famous one was discovered by Euler:

graphics/15equ08.gif


which generates only prime numbers for 80 values of n from -40 through 39, each one generated twice. An equivalent polynomial is

graphics/15equ09.gif


which simply shifts the range of values for n to 0 through 79 by replacing n with n + 40. For the values 0 through 99, the latter polynomial generates 95 prime numbers, 55 of which are distinct. (In fact, about half of the first 2,400 numbers it generates are prime.)

Another polynomial, published in 1995 by M.L. Greenwood and N. Boston, two amateur mathematicians, is

graphics/15equ10.gif


which generates 90 distinct prime numbers for values of n from 0 through 99.

Listing 15-4 shows a program that demonstrates these two polynomials. It uses our earlier primality test to check each generated number.

Listing 15-4 Prime-generating quadratic polynomials. Most of the generated numbers are prime for n from 0 through 99; composite numbers are marked with a small c .
 package numbercruncher.program15_4; import java.util.HashSet; import numbercruncher.primeutils.PrimalityTest; import numbercruncher.mathutils.AlignRight; /**  * PROGRAM 15-4:  Prime Number Generators  *  * Demonstrate two quadratic polynomials that generate prime numbers.  */ public class PrimeGenerators {     private static final String EULER     = "n^2 - 79n + 1601";     private static final String GREENWOOD = "41n^2 - 4641n + 88007";     private static final int    WIDTH     = GREENWOOD.length() + 5;     private static AlignRight ar = new AlignRight();     public static void main(String args[])     {         ar.print("n", 2);         ar.print(EULER,     WIDTH);         ar.print(GREENWOOD, WIDTH);         ar.underline();         int ePrimeCount = 0;              // count of Euler primes         int gPrimeCount = 0;              // count of Greenwood primes         HashSet ePrimes = new HashSet();  // set of Euler primes         HashSet gPrimes = new HashSet();  // set of Greenwood primes         String eMark, gMark;    // " " if prime, "c" if composite         // Loop to test generated numbers.         for (int n = 0; n <= 99; ++n) {             // Prime number generators.             int ep = n*n - 79*n + 1601;                 // Euler             int gp = Math.abs(41*n*n - 4641*n + 88007); // Greenwood             // Test for primality.             boolean epIsPrime = (new PrimalityTest(ep, 5)).test();             boolean gpIsPrime = (new PrimalityTest(gp, 5)).test();             ar.print(n, 2);             if (epIsPrime) {                 ++ePrimeCount;                 ePrimes.add(new Integer(ep));                 eMark = " ";             }             else {                 eMark = "c";             }             if (gpIsPrime) {                 ++gPrimeCount;                 gPrimes.add(new Integer(gp));                 gMark = " ";             }             else {                 gMark = "c";             }             ar.print(ep + eMark, WIDTH);             ar.print(gp + gMark, WIDTH);             ar.println();         }         ar.println();         ar.print(" ", 2);         ar.print(ePrimeCount + " primes", WIDTH);         ar.print(gPrimeCount + " primes", WIDTH);         ar.println();         ar.print(" ", 2);         ar.print(ePrimes.size() + " distinct", WIDTH);         ar.print(gPrimes.size() + " distinct", WIDTH);         ar.println();     } } 

Output:

 n          n^2 - 79n + 1601     41n^2 - 4641n + 88007 -------------------------------------------------------  0                     1601                     88007  1                     1523                     83407  2                     1447                     78889  3                     1373                     74453  4                     1301                     70099  5                     1231                     65827  6                     1163                     61637  7                     1097                     57529  8                     1033                     53503  9                      971                     49559 10                      911                     45697 11                      853                     41917c 12                      797                     38219 13                      743                     34603 14                      691                     31069 15                      641                     27617 16                      593                     24247 17                      547                     20959 18                      503                     17753c 19                      461                     14629 20                      421                     11587 21                      383                      8627 22                      347                      5749 23                      313                      2953 24                      281                       239 25                      251                      2393 26                      223                      4943 27                      197                      7411 28                      173                      9797c 29                      151                     12101 30                      131                     14323 31                      113                     16463c 32                       97                     18521 33                       83                     20497c 34                       71                     22391 35                       61                     24203 36                       53                     25933 37                       47                     27581 38                       43                     29147 39                       41                     30631 40                       41                     32033c 41                       43                     33353 42                       47                     34591 43                       53                     35747 44                       61                     36821 45                       71                     37813 46                       83                     38723 47                       97                     39551 48                      113                     40297c 49                      131                     40961 50                      151                     41543 51                      173                     42043 52                      197                     42461 53                      223                     42797 54                      251                     43051 55                      281                     43223 56                      313                     43313 57                      347                     43321 58                      383                     43247c 59                      421                     43091c 60                      461                     42853 61                      503                     42533 62                      547                     42131 63                      593                     41647 64                      641                     41081 65                      691                     40433 66                      743                     39703 67                      797                     38891 68                      853                     37997 69                      911                     37021 70                      971                     35963 71                     1033                     34823c 72                     1097                     33601 73                     1163                     32297 74                     1231                     30911 75                     1301                     29443 76                     1373                     27893 77                     1447                     26261 78                     1523                     24547 79                     1601                     22751 80                     1681c                    20873 81                     1763c                    18913 82                     1847                     16871 83                     1933                     14747 84                     2021c                    12541 85                     2111                     10253 86                     2203                      7883 87                     2297                      5431 88                     2393                      2897 89                     2491c                      281 90                     2591                      2417 91                     2693                      5197 92                     2797                      8059 93                     2903                     11003 94                     3011                     14029 95                     3121                     17137 96                     3233c                    20327 97                     3347                     23599 98                     3463                     26953 99                     3581                     30389                    95 primes                 90 primes                  55 distinct               90 distinct 

Along with finding the next Mersenne prime, mathematicians also strive to find quadratic polynomials that generate the highest percentage of primes for the largest domain of input values.


   
Top
 


Java Number Cruncher. The Java Programmer's Guide to Numerical Computing
Java Number Cruncher: The Java Programmers Guide to Numerical Computing
ISBN: 0130460419
EAN: 2147483647
Year: 2001
Pages: 141
Authors: Ronald Mak

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net