Miller–Rabin primality test: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 1,952: | Line 1,952: | ||
% is_prime/2 returns false if N is composite, true if N probably prime |
% is_prime/2 returns false if N is composite, true if N probably prime |
||
% implements a Miller-Rabin primality test and is deterministic for N < 3.415e+14, |
% implements a Miller-Rabin primality test and is deterministic for N < 3.415e+14, |
||
% and is probabilistic for larger N |
% and is probabilistic for larger N. Adapted from the Erlang version. |
||
is_prime(1, Ret) :- Ret = false, !. % 1 is non-prime |
is_prime(1, Ret) :- Ret = false, !. % 1 is non-prime |
||
is_prime(2, Ret) :- Ret = true, !. % 2 is prime |
is_prime(2, Ret) :- Ret = true, !. % 2 is prime |