Chernick's Carmichael numbers: Difference between revisions
→{{header|Phix}}: trans C
m (Phix/mpfr) |
(→{{header|Phix}}: trans C) |
||
Line 893:
</pre>
Pleasingly fast, note however that a(10) remains well out of reach / would probably need a complete rewrite.
=== with cheat ===
{{trans|C}} with added cheat for the a(10) case - I found a nice big prime factor of k and added that on each iteration instead of 1.
<lang Phix>include mpfr.e
sequence ppp = {3,5,7,11,13,17,19,23}
function primality_pretest(atom k)
for i=1 to length(ppp) do
if remainder(k,ppp[i])=0 then return (k<=23) end if
end for
return true
end function
function probprime(atom k, mpz n)
mpz_set_d(n, k)
return mpz_prime(n)
end function
function is_chernick(integer n, atom m, mpz z)
atom t = 9 * m;
if primality_pretest(6 * m + 1) == false then return false end if
if primality_pretest(12 * m + 1) == false then return false end if
for i=1 to n-3 do
if primality_pretest(t*power(2,i) + 1) == false then return false end if
end for
if probprime(6 * m + 1, z) == false then return false end if
if probprime(12 * m + 1, z) == false then return false end if
for i=1 to n-2 do
if probprime(t*power(2,i) + 1, z) == false then return false end if
end for
return true
end function
procedure main()
atom t0 = time()
mpz z = mpz_init(0)
for n=3 to 10 do
atom multiplier = iff(n>4 ? power(2,n-4) : 1), k = 1
if n>5 then multiplier *= 5 end if
while true do
if n=10 then k += 12564168 end if -- cheat!
atom m = k * multiplier;
if is_chernick(n, m, z) then
printf(1,"a(%d) has m = %d\n", {n, m})
exit
end if
k += 1
end while
end for
?elapsed(time()-t0)
end procedure
main()</lang>
{{out}}
<pre>
a(3) has m = 1
a(4) has m = 1
a(5) has m = 380
a(6) has m = 380
a(7) has m = 780320
a(8) has m = 950560
a(9) has m = 950560
a(10) has m = 3208386195840
"0.1s"
</pre>
=={{header|Raku}}==
| |||