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

[fred_76]

Miller Rabin optimized on my HP35s gives the following results. In brackets the speed compared to the brut force v3).

Code:

6 digits (999 983) in 0' 37" slower than brut force
7 digits (9 999 989) in 1' 9" slower than brut force
8 digits (99 999 989) in 1' 22" (x1.1)
9 digits (999 999 937) in 1' 27" (x3.2)
10 digits (9 999 999 967) in 2' 13" (x6.6)
11 digits (99 999 999 977) in 2' 29" (x19)
12 digits (999 999 999 989) in 2' 37" (x58)

Note that the HP48GX does 999,999,999,989 in ~ 31 seconds... it is 5x faster than the HP35S.

I use the Miller Rabin algorithm already detailed in some page before. I test only a small set of bases as it was proven that such small set is enough :

* if n < 2,047, it is enough to test a = 2;
* if n < 9,080,191, it is enough to test a = 31 and 73;
* if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
* if n < 1,122,004,669,633, it is enough to test a = 2, 13, 23, and 1662803;

The MR test is however to be used for numbers greater than about 90 000 000 as the brut force is faster for smaller number.

Well, that's quite fast for such a calculator...