Prime Number Generation
=======================
In issue 50 R.Harker (D6E) wrote a short and simple prime number
generator (program Primes1). It went up all integers in sequence testing
if any other number less than it would divide it evenly, ie if it had any
factors. In issue 51, Peter Davy (???) wrote an improved version (program
Primes2). The major improvement was that obviously, all prime numbers over
2 are odd, so only odd numbers were tested. Also, all the factors of a
number must be less than its square root. For example, 36 has factors
2, 3, 4, 6, 9, 12 and 18. The unique factors are 2 and 3 which are both
less than or equal to the square root 6. So the next logical improvement
is to only test up to the square root. The timing table shown below
shows that this improves the speed about 18 fold.
All factors of a number can be reduced themselves to prime numbers. 36 is
9 * 4 which is 3 * 3 * 2 * 2. The next logical step is to test only with
prime numbers up to the square root. This process is called the sieve of
Erastores. This would involve storing a list of all the prime numbers
encountered so far. However, by examining primes it can be seen that all
prime numbers over 3 are members of the sequence 6n-1, 6n+1. Note that
this does not mean that all members of the sequence 6n-1, 6n+1 are primes.
All cats have four legs, that dog has four legs, therefore it is a cat.
Program Primes3 uses this knowlege to extend the sieve process to test
numbers in the sequence 6n-1, 6n+1; most of which are primes; with numbers
in the sequence 6n-1, 6n+1. The slight inefficiency caused by the sequence
generating a number of non-primes is countered by the simplicity of the
formula. The timing table shows that Primes3 is about 20 times faster
than R.Harker's original.
Rewriting the program using resident integer variables speeds things up by
another third. The reduction in the length of the names and the fact that
they do not need to be searched for in Basic variable area but are in fixed
locations gives the extra burst of speed. The table shows that Primes4 is
30 times as fast as the original.
In the eighteenth century the Swiss mathematician Leonhard Eular
discovered that the formula:
f(n)=n^2+n+41
returns a large number of prime numbers. For all values of n from 0 to 39
the result is a prime. It fails at n=40 as f(n)=40^2+40+41 which is 41^2.
However, this formula generates a larger number of primes than any other
quadratic (Mathematics: The New Gold Age; Delvin, Keith; p53).
Unfortunately, this cannot be used on its own to generate primes as it
skips many primes. For example, f(3) is 53, but f(4) is 61, missing out
59. However, re-arranging the equation gives a method of testing for
primeness over a limited range.
*.
Time of Prime programs in seconds
n P(n) 1 2 3 4 5 6
10 29 1.79 0.46 0.44 0.32 0.32 0.36
100 541221.61 11.96 10.31 7.43 7.98 8.63
1000791927500331.74268.75175.77185.05195.74
Comparative speed: 1 18 20 30 29 26
I lost patience waiting for Primes1 to get to P(1000). I calculated that
it would take about 7 and a half hours to get there!