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

[Albert Chan]

What happens if you do not check each remainder goes to zero, but collect it all per turns ?
If product of the turn remainders reached zero, it meant you hit a factor there.

You do not even have to check 2,3,5,7 ! Like this:

Code:

r = (n % 2) * (n % 3) * (n % 5)
for turn in range(1, n):     # actual termination by size of factors
    # NOTE: wheel had only 7 spokes = (7,11,13,17,19,23,29) + 30*(turn-1)
    for w in primewheel(turn): r *= n % w
    if r == 0: return turn   # factor found, factor < 30*turn
    if w * w >= n: break
    r = n % (w + 2)          # last spoke, reset r to avoid overflow
return n                     # no factors