janet-lang / spork

Various Janet utility modules - the official "Contrib" library.
MIT License
117 stars 35 forks source link

Add `math/factor` #152

Closed primo-ppcg closed 1 year ago

primo-ppcg commented 1 year ago

Related: #147

Returns an array containing the prime factors of n.


- Speeds up `miller-rabin-prp?`
sogaiu commented 1 year ago

Did some testing. The following seemed to agree with an online checker.

$ JANET_PATH=~/src/spork.primo-ppcg/jpm_tree/lib ~/src/janet/build/janet 
Janet 1.30.0-d2dd241e linux/x64/gcc - '(doc)' for help

repl:1:> (upscope (import spork/math) :done)
:done

repl:2:> (math/factor 1023)
@[3 11 31]

repl:3:> (math/factor 1024)
@[2 2 2 2 2 2 2 2 2 2]

repl:4:> (math/factor (int/u64 "77777777777777777"))
@[<core/u64 7> <core/u64 2071723> <core/u64 5363222357>]

repl:5:> (math/factor (int/u64 "1888888881188888888"))
@[<core/u64 2> <core/u64 2> <core/u64 2> <core/u64 41> <core/u64 5758807564600271>]

repl:6:> (math/factor (int/u64 "547716131821"))
@[<core/u64 547716131821>]