Anonymous user
Miller–Rabin primality test: Difference between revisions
no edit summary
m (→{{header|D}}) |
No edit summary |
||
Line 710:
[907,911,919,929,937,941,946,947,953,967,971,977,983,991,997]
</pre>
=={{header|Icon}} and {{header|Unicon}}==
The following code works in both languages:
<lang unicon>procedure main()
every "probably prime" == primeTest(n := 901 to 1000, 10) do
write(n," is probably prime")
end
procedure primeTest(n, k)
if n = 2 then return "probably prime"
if n%2 = 0 then return "composite"
s := 0
d := n-1
while (d%2 ~= 0, s+:=1, d/:=2)
every (1 to k, x := ((2+?(n-2))^d)%n) do {
if x = (1 | (n-1)) then next
every (1 to s-1, x := (x^2)%n) do {
if x = 1 then return "composite"
if x = n-1 then break next
}
return "composite"
}
return "probably prime"
end</lang>
Sample run:
<pre>->mrpt
907 is probably prime
911 is probably prime
919 is probably prime
929 is probably prime
937 is probably prime
941 is probably prime
947 is probably prime
953 is probably prime
967 is probably prime
971 is probably prime
977 is probably prime
983 is probably prime
991 is probably prime
997 is probably prime
-></pre>
=={{header|J}}==
|