Anonymous user
Miller–Rabin primality test: Difference between revisions
→{{header|Crystal}}
Line 1,031:
# Returns true if +self+ is a prime number, else returns false.
def primemr?
raise ArgumentError.new "Input must be non-negative integer" if self < 0
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}
return primes.includes? self if self <= primes.last
modp47 = 614_889_782_588_491_410
return false if modp47.gcd(self.to_big_i) != 1 # eliminates 86.2% of all integers
# wits = [range, [wit_prms]] or nil
wits = WITNESS_RANGES.find {|range, wits| range >
witnesses = wits && wits[1] || primes
miller_rabin_test(witnesses)
Line 1,073:
# Best known deterministic witnesses for given range and set of bases
# https://miller-rabin.appspot.com/
# https://en.wikipedia.org/wiki/Miller%E2%80%
private WITNESS_RANGES = {
341_531 => {9345883071009581737},
| |||