[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin)

[Thomas Klemm]

(02-14-2019 06:26 PM)Albert Chan Wrote:  What happens if you do not check each remainder goes to zero, but collect it all per turns ?

Here's a program for the HP-42S using this idea:

Code:

00 { 120-Byte Prgm }
01▸LBL "PRIME?"
02 STO 09
03 1
04 STO 00
05 7
06 STO 01
07 11
08 STO 02
09 13
10 STO 03
11 17
12 STO 04
13 19
14 STO 05
15 23
16 STO 06
17 29
18 STO 07
19 30
20 STO 08
21 RCL 09
22 RCL 09
23 RCL 09
24 2
25 MOD
26 X<>Y
27 3
28 MOD
29 ×
30 X<>Y
31 5
32 MOD
33 ×
34▸LBL 00
35 X<>Y
36 RCL 01
37 MOD
38 ×
39 X<>Y
40 RCL 02
41 MOD
42 ×
43 X<>Y
44 RCL 03
45 MOD
46 ×
47 X<>Y
48 RCL 04
49 MOD
50 ×
51 X<>Y
52 RCL 05
53 MOD
54 ×
55 X<>Y
56 RCL 06
57 MOD
58 ×
59 X<>Y
60 RCL 07
61 MOD
62 ×
63 X=0?
64 RTN
65 CLX
66 RCL 07
67 X↑2
68 X>Y?
69 RTN
70 CLX
71 RCL 08
72 STO+ 00
73 STO+ 01
74 STO+ 02
75 STO+ 03
76 STO+ 04
77 STO+ 05
78 STO+ 06
79 STO+ 07
80 CLX
81 RCL 00
82 MOD
83 GTO 00
84 END

Translation should be straight forward for the HP-35s or pretty much any calculator that supports MOD and register arithmetics.

It works only for input > 29 and returns 0 for composite numbers.
In this case one of the numbers in registers 00-07 is a factor.
Otherwise it returns a number a bit bigger than the input.

Examples:

24883
XEQ "PRIME?"
y: 24883
x: 0

24883 = 149 × 167

99999999977
XEQ "PRIME?"
y: 99999999977
x: 100000780441

99999999977 is a prime.

Cheers
Thomas