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

[Albert Chan]

(02-14-2019 01:10 PM)fred_76 Wrote:  Version 3 Run time
6 digits 999 983 0m 9.8s (about 2x faster than V0)
7 digits 9 999 991 0m 28s
8 digits 99 999 989 1m 28s
9 digits 999 999 937 4m 36s
10 digits 9 999 999 967 14m 37s
11 digits 99 999 999 977 46m 26s
12 digits 999 999 999 989 2h 32m 18s

Curious about performance of checks vs. size of N
Redo above tables, with cases checked = 4 + 8 * ceil((√(N) - 7)/30)

Code:

Digits Time(sec) Checks  Speed(msec per check)
6      9.8       276     35.5
7      28        852     32.9
8      88        2676    32.9
9      276       8434    32.7
10     877       26676   32.9
11     2786      84332   33.0
12     9138      266676  34.3

It seems check speed unaffected by size of N.
Timings depends mainly on number of checks required.

It is possible to reduce required checks, by few applications of Fermat's method.
Example, N = 999,999,999,989. Tried to complete the squares:

Code:

X          Y^2 = X^2-N
1e6        11
1e6 + 1    2e6 + 1 + 11
1e6 + 2    4e6 + 3 + 12
1e6 + 3    6e6 + 5 + 15
1e6 + 4    8e6 + 7 + 20
1e6 + 5    10e6 + 9 + 27
1e6 + 6    12e6 + 11 + 36
1e6 + 7    14e6 + 13 + 47
1e6 + 8    16e6 + 15 + 60
1e6 + 9    18e6 + 17 + 75

If Y is integer, above can be factored as (X + Y)(X - Y)
None of above Y's worked, but it reduce cases checked greatly.
(BTW, only the Y^2 ends in 36 need checking, others will never be integer square)

Max factors to search = floor(next(X) - next(Y)) = floor((1e6 + 10) - √(20e6 + 19 + 92)) = 995537
-> Cases to check = 4 + 8 * ceil((995537 - 7) / 30) = 4 + 8 * 33185 = 265484
-> Removed checks = 266676 - 265484 = 1192 (or, 1192/8 = 149 turns)