Carmichael 3 strong pseudoprimes: Difference between revisions
no edit summary
(Add Swift) |
No edit summary |
||
Line 2,065:
61 x 241 x 421
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>
| |||