Anonymous user
Miller–Rabin primality test: Difference between revisions
Add Seed7 example
(Added Racket code) |
(Add Seed7 example) |
||
Line 2,146:
[funEnd]
END FUNCTION</lang>
=={{header|Seed7}}==
<lang seed7>$ include "seed7_05.s7i";
include "bigint.s7i";
const func boolean: millerRabin (in bigInteger: n, in integer: k) is func
result
var boolean: probablyPrime is TRUE;
local
var bigInteger: d is 0_;
var integer: r is 0;
var integer: s is 0;
var bigInteger: a is 0_;
var bigInteger: x is 0_;
var integer: tests is 0;
begin
if n < 2_ or (n > 2_ and not odd(n)) then
probablyPrime := FALSE;
elsif n > 3_ then
d := pred(n);
s := lowestSetBit(d);
d >>:= s;
while tests < k and probablyPrime do
a := rand(2_, pred(n));
x := modPow(a, d, n);
if x <> 1_ and x <> pred(n) then
r := 1;
while r < s and x <> 1_ and x <> pred(n) do
x := modPow(x, 2_, n);
incr(r);
end while;
probablyPrime := x = pred(n);
end if;
incr(tests);
end while;
end if;
end func;
const proc: main is func
local
var bigInteger: number is 0_;
begin
for number range 2_ to 1000_ do
if millerRabin(number, 10) then
writeln(number);
end if;
end for;
end func;</lang>
Original source: [http://seed7.sourceforge.net/algorith/math.htm#millerRabin]
=={{header|Smalltalk}}==
| |||