Miller–Rabin primality test: Difference between revisions
Content added Content deleted
| Line 3,212: | Line 3,212: | ||
proc primemr*[T: SomeInteger](n: T): bool = |
proc primemr*[T: SomeInteger](n: T): bool = |
||
let primes = @[2u64, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] |
let primes = @[2u64, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] |
||
if n <= |
if n <= primes[^1].T: return (n in primes) # for n <= primes.last |
||
let modp47 = 614889782588491410u # => primes.product, largest < 2^64 |
let modp47 = 614889782588491410u # => primes.product, largest < 2^64 |
||
if gcd(n, modp47) != 1: return false # eliminates 86.2% of all integers |
if gcd(n, modp47) != 1: return false # eliminates 86.2% of all integers |
||