Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
(Add Swift) |
No edit summary |
||
Line 2,065: | Line 2,065: | ||
61 x 241 x 421 |
61 x 241 x 421 |
||
61 x 3361 x 4021 |
61 x 3361 x 4021 |
||
</pre> |
|||
=={{header|Prolog}}== |
|||
<lang prolog> |
|||
show(Limit) :- |
|||
forall( |
|||
carmichael(Limit, P1, P2, P3, C), |
|||
format("~w * ~w * ~w ~t~20| = ~w~n", [P1, P2, P3, C])). |
|||
carmichael(Upto, P1, P2, P3, X) :- |
|||
between(2, Upto, P1), |
|||
prime(P1), |
|||
Limit is P1 - 1, between(2, Limit, H3), |
|||
MaxD is H3 + P1 - 1, between(1, MaxD, D), |
|||
(H3 + P1)*(P1 - 1) mod D =:= 0, |
|||
-P1*P1 mod H3 =:= D mod H3, |
|||
P2 is 1 + (P1 - 1)*(H3 + P1) div D, |
|||
prime(P2), |
|||
P3 is 1 + P1*P2 div H3, |
|||
prime(P3), |
|||
X is P1*P2*P3. |
|||
wheel235(L) :- |
|||
W = [4, 2, 4, 2, 4, 6, 2, 6 | W], |
|||
L = [1, 2, 2 | W]. |
|||
prime(N) :- N < 2, !, false. |
|||
prime(N) :- |
|||
wheel235(W), |
|||
prime(N, 2, W). |
|||
prime(N, D, _) :- D*D > N, !. |
|||
prime(N, D, _) :- N mod D =:= 0, !, false. |
|||
prime(N, D, [A|As]) :- D2 is D + A, prime(N, D2, As). |
|||
</lang> |
|||
{{Out}} |
|||
<pre> |
|||
?- show(61). |
|||
3 * 11 * 17 = 561 |
|||
5 * 29 * 73 = 10585 |
|||
5 * 17 * 29 = 2465 |
|||
5 * 13 * 17 = 1105 |
|||
7 * 19 * 67 = 8911 |
|||
7 * 31 * 73 = 15841 |
|||
7 * 13 * 31 = 2821 |
|||
7 * 23 * 41 = 6601 |
|||
7 * 73 * 103 = 52633 |
|||
7 * 13 * 19 = 1729 |
|||
11 * 29 * 107 = 34133 |
|||
11 * 37 * 59 = 24013 |
|||
13 * 61 * 397 = 314821 |
|||
13 * 37 * 241 = 115921 |
|||
13 * 97 * 421 = 530881 |
|||
13 * 37 * 97 = 46657 |
|||
13 * 37 * 61 = 29341 |
|||
17 * 41 * 233 = 162401 |
|||
17 * 353 * 1201 = 7207201 |
|||
17 * 23 * 79 = 30889 |
|||
17 * 53 * 101 = 91001 |
|||
19 * 43 * 409 = 334153 |
|||
19 * 139 * 661 = 1745701 |
|||
19 * 59 * 113 = 126673 |
|||
19 * 193 * 283 = 1037761 |
|||
19 * 199 * 271 = 1024651 |
|||
23 * 59 * 227 = 308039 |
|||
23 * 71 * 137 = 223721 |
|||
23 * 199 * 353 = 1615681 |
|||
23 * 83 * 107 = 204263 |
|||
23 * 43 * 53 = 52417 |
|||
29 * 113 * 1093 = 3581761 |
|||
29 * 197 * 953 = 5444489 |
|||
29 * 149 * 541 = 2337661 |
|||
29 * 41 * 109 = 129601 |
|||
29 * 89 * 173 = 446513 |
|||
29 * 97 * 149 = 419137 |
|||
31 * 991 * 15361 = 471905281 |
|||
31 * 67 * 1039 = 2158003 |
|||
31 * 61 * 631 = 1193221 |
|||
31 * 151 * 1171 = 5481451 |
|||
31 * 223 * 1153 = 7970689 |
|||
31 * 61 * 271 = 512461 |
|||
31 * 79 * 307 = 751843 |
|||
31 * 61 * 211 = 399001 |
|||
31 * 271 * 601 = 5049001 |
|||
31 * 181 * 331 = 1857241 |
|||
31 * 313 * 463 = 4492489 |
|||
31 * 73 * 79 = 178777 |
|||
37 * 109 * 2017 = 8134561 |
|||
37 * 73 * 541 = 1461241 |
|||
37 * 613 * 1621 = 36765901 |
|||
37 * 73 * 181 = 488881 |
|||
37 * 73 * 109 = 294409 |
|||
41 * 1721 * 35281 = 2489462641 |
|||
41 * 881 * 12041 = 434932961 |
|||
41 * 89 * 1217 = 4440833 |
|||
41 * 97 * 569 = 2262913 |
|||
41 * 101 * 461 = 1909001 |
|||
41 * 241 * 761 = 7519441 |
|||
41 * 241 * 521 = 5148001 |
|||
41 * 73 * 137 = 410041 |
|||
41 * 61 * 101 = 252601 |
|||
43 * 631 * 13567 = 368113411 |
|||
43 * 271 * 5827 = 67902031 |
|||
43 * 127 * 2731 = 14913991 |
|||
43 * 139 * 1993 = 11912161 |
|||
43 * 127 * 1093 = 5968873 |
|||
43 * 157 * 751 = 5070001 |
|||
43 * 107 * 461 = 2121061 |
|||
43 * 211 * 757 = 6868261 |
|||
43 * 67 * 241 = 694321 |
|||
43 * 631 * 1597 = 43331401 |
|||
43 * 131 * 257 = 1447681 |
|||
43 * 199 * 373 = 3191761 |
|||
43 * 127 * 211 = 1152271 |
|||
43 * 211 * 337 = 3057601 |
|||
43 * 433 * 643 = 11972017 |
|||
43 * 547 * 673 = 15829633 |
|||
43 * 3361 * 3907 = 564651361 |
|||
47 * 101 * 1583 = 7514501 |
|||
47 * 53 * 499 = 1243009 |
|||
47 * 107 * 839 = 4219331 |
|||
47 * 3359 * 6073 = 958762729 |
|||
47 * 1151 * 1933 = 104569501 |
|||
47 * 157 * 239 = 1763581 |
|||
47 * 3727 * 5153 = 902645857 |
|||
47 * 89 * 103 = 430849 |
|||
53 * 113 * 1997 = 11960033 |
|||
53 * 157 * 2081 = 17316001 |
|||
53 * 79 * 599 = 2508013 |
|||
53 * 157 * 521 = 4335241 |
|||
53 * 281 * 877 = 13061161 |
|||
53 * 197 * 233 = 2432753 |
|||
59 * 131 * 1289 = 9962681 |
|||
59 * 139 * 821 = 6733021 |
|||
59 * 149 * 587 = 5160317 |
|||
59 * 173 * 379 = 3868453 |
|||
59 * 179 * 353 = 3728033 |
|||
59 * 1451 * 2089 = 178837201 |
|||
61 * 421 * 12841 = 329769721 |
|||
61 * 181 * 5521 = 60957361 |
|||
61 * 1301 * 19841 = 1574601601 |
|||
61 * 277 * 2113 = 35703361 |
|||
61 * 181 * 1381 = 15247621 |
|||
61 * 541 * 3001 = 99036001 |
|||
61 * 661 * 2521 = 101649241 |
|||
61 * 1009 * 2677 = 164766673 |
|||
61 * 271 * 571 = 9439201 |
|||
61 * 241 * 421 = 6189121 |
|||
61 * 3361 * 4021 = 824389441 |
|||
true. |
|||
</pre> |
</pre> |
||