Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(added Julia example) |
|||
| Line 1,288: | Line 1,288: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
The built-in <code>isprime</code> function uses the Miller-Rabin primality test. Here is the implementation of <code>isprime</code> from the Julia standard library (Julia version 0.2): |
The built-in <code>isprime</code> function uses the Miller-Rabin primality test. Here is the implementation of <code>isprime</code> from the Julia standard library (Julia version 0.2): |
||
<lang julia> |
<lang julia> |
||
witnesses(n::Union(Uint8,Int8,Uint16,Int16)) = (2,3) |
|||
witnesses(n::Union(Uint32,Int32)) = n < 1373653 ? (2,3) : (2,7,61) |
|||
witnesses(n::Union(Uint64,Int64)) = |
|||
n < 1373653 ? (2,3) : |
|||
n < 4759123141 ? (2,7,61) : |
|||
n < 2152302898747 ? (2,3,5,7,11) : |
|||
n < 3474749660383 ? (2,3,5,7,11,13) : |
|||
(2,325,9375,28178,450775,9780504,1795265022) |
|||
function isprime(n::Integer) |
|||
n == 2 && return true |
n == 2 && return true |
||
(n < 2) | iseven(n) && return false |
(n < 2) | iseven(n) && return false |
||
| Line 1,300: | Line 1,310: | ||
while x != n-1 |
while x != n-1 |
||
(t-=1) <= 0 && return false |
(t-=1) <= 0 && return false |
||
x = oftype(n, widemul(x,x) % n) |
x = oftype(n, Base.widemul(x,x) % n) |
||
x == 1 && return false |
x == 1 && return false |
||
end |
end |
||