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

[Gerald H]

(02-13-2019 11:53 AM)Thomas Klemm Wrote:  You may want to have a look at (35S) Number Theory Library.
There are the following functions:

Quote:PRIME? 148
A -> 0 OR 1 as A is composite or probably prime.

RABIN? 571
A, B -> 0 or 1, 1 if A is a strong pseudo-prime base B, 0 if not.

Though I haven't tried but if PRIME? uses RABIN? (which I assume implements the Miller-Rabin Primality Test) it might be considerably faster for bigger numbers.

I've implemented this for the HP-48GX:
(48G) Miller-Rabin Primality Test

This article gives a bit more details:
Miller-Rabin Primality Test for the HP-48

Cheers
Thomas

Yes, PRIME? calls RABIN? to one random base after first checking for small factors of A.