46 lines
1.1 KiB
Text
46 lines
1.1 KiB
Text
$ 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;
|