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

-------------------------------------------------------------------------------

Back