Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
(→{{header|F_Sharp|F#}}: Use extensible prime generator) |
No edit summary |
||
Line 2,020: | Line 2,020: | ||
<pre> |
<pre> |
||
──────── 8716 Carmichael numbers found. |
──────── 8716 Carmichael numbers found. |
||
</pre> |
|||
=={{header|Ring}}== |
|||
<lang ring> |
|||
# Project : Carmichael 3 strong pseudoprimes |
|||
# Date : 2017/11/29 |
|||
# Author : Gal Zsolt (~ CalmoSoft ~) |
|||
# Email : <calmosoft@gmail.com> |
|||
see "The following are Carmichael munbers for p1 <= 61:" + nl |
|||
see "p1 p2 p3 product" + nl |
|||
for p = 2 to 61 |
|||
carmichael3(p) |
|||
next |
|||
func carmichael3(p1) |
|||
if isprime(p1) = 0 return ok |
|||
for h3 = 1 to p1 -1 |
|||
t1 = (h3 + p1) * (p1 -1) |
|||
t2 = (-p1 * p1) % h3 |
|||
if t2 < 0 |
|||
t2 = t2 + h3 |
|||
ok |
|||
for d = 1 to h3 + p1 -1 |
|||
if t1 % d = 0 and t2 = (d % h3) |
|||
p2 = 1 + (t1 / d) |
|||
if isprime(p2) = 0 |
|||
loop |
|||
ok |
|||
p3 = 1 + floor((p1 * p2 / h3)) |
|||
if isprime(p3) = 0 or ((p2 * p3) % (p1 -1)) != 1 |
|||
loop |
|||
ok |
|||
see "" + p1 + " " + p2 + " " + p3 + " " + p1*p2*p3 + nl |
|||
ok |
|||
next |
|||
next |
|||
func isprime(num) |
|||
if (num <= 1) return 0 ok |
|||
if (num % 2 = 0) and num != 2 |
|||
return 0 |
|||
ok |
|||
for i = 3 to floor(num / 2) -1 step 2 |
|||
if (num % i = 0) |
|||
return 0 |
|||
ok |
|||
next |
|||
return 1 |
|||
</lang> |
|||
Output: |
|||
<pre> |
|||
The following are Carmichael munbers for p1 <= 61: |
|||
p1 p2 p3 product |
|||
== == == ======= |
|||
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 |
|||
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 |
|||
19 43 409 334153 |
|||
19 199 271 1024651 |
|||
23 199 353 1615681 |
|||
29 113 1093 3581761 |
|||
29 197 953 5444489 |
|||
31 991 15361 471905281 |
|||
31 61 631 1193221 |
|||
31 151 1171 5481451 |
|||
31 61 271 512461 |
|||
31 61 211 399001 |
|||
31 271 601 5049001 |
|||
31 181 331 1857241 |
|||
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 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 127 1093 5968873 |
|||
43 211 757 6868261 |
|||
43 631 1597 43331401 |
|||
43 127 211 1152271 |
|||
43 211 337 3057601 |
|||
43 433 643 11972017 |
|||
43 547 673 15829633 |
|||
43 3361 3907 564651361 |
|||
47 3359 6073 958762729 |
|||
47 1151 1933 104569501 |
|||
47 3727 5153 902645857 |
|||
53 157 2081 17316001 |
|||
53 79 599 2508013 |
|||
53 157 521 4335241 |
|||
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 271 571 9439201 |
|||
61 241 421 6189121 |
|||
61 3361 4021 824389441 |
|||
</pre> |
</pre> |
||