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

[fred_76]

(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 ?
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

You are right, this would simplify the code. But unfortunately, at least on the HP35s, the instruction x=0? (about 3 ms) is 4x faster than STO*Var (about 12 ms). Thus you will end-up with a run time increased by a factor of about 4.