Milyen gyorsan ellenőrizni egy egyszerű számot
K:> 2.3.3.1 Hogyan lehet gyorsan ellenőrizni egy egyszerű számot?
A:> Itt van a program. Nagyon gyorsan és pontosan működik. Sajnos a fakka korábbi verziójában ez a program hibát tartalmazott. Most úgy tűnik, mintha nem. =)
függvény mulmod (x, y, m: longint): longint; szerelő;
asm
mov eax, x
mul y
div m
mov eax, edx
végén;
függvény powmod (x, a, m: longint): longint;
var
r: longint;
kezdődik
r: = 1;
míg a> 0 nem
kezdődik
ha furcsa (a) akkor r: = mulmod (r, x, m);
a: = a shr 1;
x: = mulmod (x, x, m);
végén;
powmod: = r;
végén;
function isprime (p: longint): logikai;
var q, i, a: longint;
const görbék = 20;
kezdődik
ha furcsa (p), akkor
kezdődik
isprime: = igaz;
q: = p-1;
miközben nem furcsa (q) do q: = q shr 1;
i: = 1 fordulóban
kezdődik
a: = Véletlen (p-2) +2;
ha a powmod (a, p-1, p)<>1 majd
kezdődik
isprime: = hamis;
break;
végén;
a: = powmod (a, q, p);
ha a<>1 majd
kezdődik
míg (a<>1) és (a<>p-1) a: = mulmod (a, a, p);
ha a = 1 akkor
kezdődik
isprime: = hamis;
break;
végén;
végén;
végén;
end else isprime: = (p = 2);
végén;
var t: longint;
kezdődik
Véletlenszerű;
t: = 1000000000-től 1000100000-ig, ha isprime (t), akkor írjon (t);
végén.
V:> Ezenkívül az algoritmus egy másik verziója: a Zyuzik példaprogramja
(bár lassabbnak tűnik, mint az előző).
Az első oldalra