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

[Albert Chan]

Trivia: searching backwards, found a particular bad composite, with many SPRP non-witnesses.

N = 999999 512881 = 881917 * 1133893 = A*B

For PRP test:
Total PRP non-witnesses = gcd(A-1,N-1) gcd(B-1,N-1) = 125988 * 125988 = 15872 976144
Percent of hitting PRP non-witness = (125988² - 2) / (N-3) ≈ 1.59%

For SPRP test:
Tried first 10 million bases, SPRP non-witnesses = 59708
Percent of hitting SPRP non-witness ≈ 59708/1e7 ≈ 0.60%

Note: 0.60% assumed statstical trend continued all the way to N-2