Primzahlen mit dem HP-19C

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.  ***

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.