The original version of this file had lost all the TABs which destroyed the table at the end. I've changed it so it uses spaces to align the figures. JGH. 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 3, 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. Table of Comparative Program Times ---------------------------------- 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 541 221.61 11.96 10.31 7.43 7.98 8.63 1000 7919 27500 331.74 268.75 175.77 185.05 195.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!