Die Faszination der Primzahlen lässt sich bis in die Antike zurückverfolgen. Bereits Euklid konnte im 3. Jh. v. Chr. zeigen, dass es unendlich viele Primzahlen gibt. Trotzdem sind viele Vermutungen bis heute nicht bewiesen und die Primzahlen bilden damit ein hochaktuelles mathematisches Forschungsgebiet. Um bahnbrechende neue Entdeckungen über Primzahlen zu machen, eignen sich HP Taschenrechner wohl kaum, dafür sind sie doch ein bisschen zu langsam. Das zeigt auch das Programm für den HP-19C, auf das ich kürzlich beim Stöbern gestossen bin. Es berechnet die Primzahlen bis 10’000 und braucht dafür mehr als 15 Stunden. Trotzdem möchte ich dieses Programm an dieser Stelle erwähnen und ich habe dazu auch ein Zeitraffer-Video der Berechnung gemacht.
Nachfolgend noch der Artikel aus dem BYTE Magazine Volume 05 Number 10 (Oktober 1980), Seite 54ff.
Prime Numbers on the HP-19C
Wilfred Aslan, 26 Twin Brooks Dr, Willow Grove PA 19090
A few months back, a neighbor proudly showed me a program she had developed for her first computer science course. As James R Lewis speculated in his article „TRS-80 Performance Evaluation by Program Timing“ (see March 1980 BYTE, page 84), the program concerned the determination of prime numbers. Intrigued, I spent some time on this subject working with my little Hewlett-Packard HP-19C programmable printing calculator. Assuming that Lewis has rekindled interest in the competitive programmer’s desire for fast programs, I offer a more efficient means for the test of a prime number.
In the classic algorithm, the number being tested is always odd, because even numbers are divisible by 2. The number being tested is divided by a series of odd numbers, starting with three, and progressing by twos. If the remainder of each successive division includes fractions, the number must be prime. The trick, of course, is knowing when to stop dividing.
A moment’s reflection will show that as the value of the divisor progresses beyond the square root of the number under test, the quotients will all be smaller than the square root. Since numbers less than the square root have already been tried, further testing is pointless.
By limiting the tests in this way, the number of loops necessary may be reduced significantly. In the „Lewis Test“ of numbers to 10,000, the largest prime number is 9973, and his program uses test divisors to half that (4986.5), requiring 2491 executions of the loop. By using a divisor limit of 99 (the square root is actually 99.86), the loop need only be executed forty-eight times. On the HP-19C, this gives times of 38 m 18.1 s (for the original test) versus 46.4 s (testing only to the square root limit). For the complete computation of primes up to 10,000, the little calculator finished the assignment in 15 h 16 m 22.7 s, using the square-root limit. Listing 1 shows the program; listing 2 contains the beginning and end of my list of prime numbers.
Listing 1: A program which calculates the prime numbers to 10,000, using the square-root test limit. This listing is for the HP-19C calculator, which finished the job in just over fifteen hours.
01 *LBL0 25 14 00 02 1 01 03 PRTX 65 04 STO1 45 01 05 2 02 06 PRTX 65 07 3 03 08 PRTX 65 09 STO2 45 02 10 EEX 23 11 2 02 12 STO4 45 04 13 *LBL1 25 14 01 14 2 02 15 ST+2 45 41 02 16 RCL2 55 02 17 ?X 16 53 18 STO3 45 03 19 RCL4 55 04 20 X>Y? 16 41 21 GTO2 14 02 22 R/S 64 23 *LBL2 25 14 02 24 2 02 25 ST+1 45 41 01 26 RCL1 55 01 27 RCL3 55 03 28 X?Y 11 29 X?Y? 16 31 30 GTO3 14 03 31 RCL2 55 02 32 PRTX 65 33 1 01 34 STO1 45 01 35 GTO1 14 01 36 *LBL3 25 14 03 37 RCL2 55 02 38 RCL1 55 01 39 ÷ 61 40 FRC 25 52 41 X?0? 25 51 42 GTO2 14 02 43 1 01 44 STO1 45 01 45 GTO1 14 01 46 R/S 64
Listing 2: The beginning and end of the program when run to calculate all primes up to 10,000.
1. 2. 3. 5. *** 7. *** 11. *** 13. *** 17. *** 19. *** 23. *** 29. *** 31. *** 9871. *** 9883. *** 9887. *** 9901. *** 9907. *** 9923. *** 9929. *** 9931. *** 9941. *** 9949. *** 9967. *** 9973. ***
Nachtrag
Mit Freude habe ich festgestellt, dass mein Video andere Leute inspiriert hat, noch tiefer in dieses Thema einzutauchen, siehe dazu: