DAVID W. DELEY
DOCUMENTATION ON PROGRAM NEXTPRIME.FOR
Here's a routine NEXTPRIME that will return the next prime number
greater than or equal to a given input number. With the current
database of the first 168 primes, it's guaranteed to return the next
prime for all numbers less than 1,018,081. For numbers greater than
that, it returns numbers which are relatively prime to all numbers below
1,018,801. (Note 1,018,801 = 1009^2, and 1009 is the 169th prime
number.) The database can easily be expanded to whatever size desired.
This routine does pretty well because of the relative density of prime
numbers.
Here are some statistics for prime numbers below (and slightly above)
one million:
Of the first 10000 primes:
the 9592th prime is 99991, the last prime below 1 million
The maximum difference between consecutive primes is: 72
which occurs between prime 31397 and 31469
The average difference between primes is: 10.4907160
The standard deviation of the differences between consecutive
primes is: 8.0989161
--------------------------------------------------------------------
Here are the statistics for the NEXTPRIME routine:
I statistically tested the number of times the routine NEXTPRIME
calculated the MOD function, which is the main thing it does in the main
loop. Below I summarized the number of times it executes the following
line in the code:
IF ( MOD(NUMBER,PRIMES(I)) .EQ. 0 ) THEN !it's not prime
The number of times through the main loop calculating the MOD function
seems to increase as the initial number increases:
For numbers in the range [1001,10000]
the average was 26.3
the max was 117
for the value 9974
the standard deviation was 0.21
For numbers in the range [10001,50000]
the average was 46.3
the max was 309
for the value 31398
the standard deviation was 0.18
For numbers in the range [50001,100000]
the average was 41
the max was 387
for the value 89690
the standard deviation was 0.08
-------------------------------------------------------------------------------