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

[Albert Chan]

(04-11-2019 03:18 PM)fred_76 Wrote:  Adding brut force to find factors of for "small numbers"

1) I have also merged the "brut force" with the "MR" so that numbers smaller than 20 359 000 will be analysed by brut force, and greater by MR, because MR is slower than brut force for numbers smaller than 20 359 000.

2) When a number is found to be composite, it goes to brut force to find factors. When a factor is found, the quotient is sent back to MR to check if it is composite or prime, and so on. Brut force is however very slow to find factors if they are big. For example it takes only 34s for MR to say 999 999 998 479 is composite, but 2h30 for Brut Force to find its factors...

If you have built "MR", there is no point doing "brute force".
For example, I just created factor.lua, using Pollard's rho Algorithm.

My code do 3 deltas for efficiency, but only 1 is really needed.
Example, this is from my 7 years old laptop.

lua> p = require 'factor'

lua> n = 999999998479
lua> n, '=', table.concat(p.factor(n), ' * ') -- Lua 5.4 time ~ 1.8 msec
999999998479 = 999961 * 1000039

lua> n = 2^53-1
lua> n, '=', table.concat(p.factor(n), ' * ') -- Lua 5.4 time ~ 0.6 msec
9007199254740991 = 6361 * 69431 * 20394401

Edit: updated factor.lua by replacing MOD n for the delta, and use ABS instead. Speed up ~ 5%

Note: Luajit does not work properly with this code. It uses the naive a % b = a - floor(b/a) * a
This is my Floor-Mod patch for Luajit 1.18: https://github.com/LuaJIT/LuaJIT/issues/493