Anonymous user
Carmichael 3 strong pseudoprimes: Difference between revisions
→{{header|Lua}}
(Added C++ solution) |
|||
Line 1,841:
{{out}}
See D output.
=={{header|Lua}}==
<lang lua>local function isprime(n)
if n < 2 then return false end
if n % 2 == 0 then return n==2 end
if n % 3 == 0 then return n==3 end
local f, limit = 5, math.sqrt(n)
while (f <= limit) do
if n % f == 0 then return false end; f=f+2
if n % f == 0 then return false end; f=f+4
end
return true
end
local function carmichael3(p)
local list = {}
if not isprime(p) then return list end
for h = 2, p-1 do
for d = 1, h+p-1 do
if ((h + p) * (p - 1)) % d == 0 and (-p * p) % h == (d % h) then
local q = 1 + math.floor((p - 1) * (h + p) / d)
if isprime(q) then
local r = 1 + math.floor(p * q / h)
if isprime(r) and (q * r) % (p - 1) == 1 then
list[#list+1] = { p=p, q=q, r=r }
end
end
end
end
end
return list
end
local found = 0
for p = 2, 61 do
local list = carmichael3(p)
found = found + #list
table.sort(list, function(a,b) return (a.p<b.p) or (a.p==b.p and a.q<b.q) or (a.p==b.p and a.q==b.q and a.r<b.r) end)
for k,v in ipairs(list) do
print(string.format("%.f × %.f × %.f = %.f", v.p, v.q, v.r, v.p*v.q*v.r))
end
end
print(found.." found.")</lang>
{{out}}
<pre style="height:30ex;overflow:scroll">3 × 11 × 17 = 561
5 × 13 × 17 = 1105
5 × 17 × 29 = 2465
5 × 29 × 73 = 10585
7 × 13 × 19 = 1729
7 × 13 × 31 = 2821
7 × 19 × 67 = 8911
7 × 23 × 41 = 6601
7 × 31 × 73 = 15841
7 × 73 × 103 = 52633
13 × 37 × 61 = 29341
13 × 37 × 97 = 46657
13 × 37 × 241 = 115921
13 × 61 × 397 = 314821
13 × 97 × 421 = 530881
17 × 41 × 233 = 162401
17 × 353 × 1201 = 7207201
19 × 43 × 409 = 334153
19 × 199 × 271 = 1024651
23 × 199 × 353 = 1615681
29 × 113 × 1093 = 3581761
29 × 197 × 953 = 5444489
31 × 61 × 211 = 399001
31 × 61 × 271 = 512461
31 × 61 × 631 = 1193221
31 × 151 × 1171 = 5481451
31 × 181 × 331 = 1857241
31 × 271 × 601 = 5049001
31 × 991 × 15361 = 471905281
37 × 73 × 109 = 294409
37 × 73 × 181 = 488881
37 × 73 × 541 = 1461241
37 × 109 × 2017 = 8134561
37 × 613 × 1621 = 36765901
41 × 61 × 101 = 252601
41 × 73 × 137 = 410041
41 × 101 × 461 = 1909001
41 × 241 × 521 = 5148001
41 × 241 × 761 = 7519441
41 × 881 × 12041 = 434932961
41 × 1721 × 35281 = 2489462641
43 × 127 × 211 = 1152271
43 × 127 × 1093 = 5968873
43 × 127 × 2731 = 14913991
43 × 211 × 337 = 3057601
43 × 211 × 757 = 6868261
43 × 271 × 5827 = 67902031
43 × 433 × 643 = 11972017
43 × 547 × 673 = 15829633
43 × 631 × 1597 = 43331401
43 × 631 × 13567 = 368113411
43 × 3361 × 3907 = 564651361
47 × 1151 × 1933 = 104569501
47 × 3359 × 6073 = 958762729
47 × 3727 × 5153 = 902645857
53 × 79 × 599 = 2508013
53 × 157 × 521 = 4335241
53 × 157 × 2081 = 17316001
59 × 1451 × 2089 = 178837201
61 × 181 × 1381 = 15247621
61 × 181 × 5521 = 60957361
61 × 241 × 421 = 6189121
61 × 271 × 571 = 9439201
61 × 277 × 2113 = 35703361
61 × 421 × 12841 = 329769721
61 × 541 × 3001 = 99036001
61 × 661 × 2521 = 101649241
61 × 1301 × 19841 = 1574601601
61 × 3361 × 4021 = 824389441
69 found.</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
| |||