Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
m (→Source: Add a hint to an orphaned phrase.) |
(Added Go) |
||
Line 736: | Line 736: | ||
61 * 241 * 421 |
61 * 241 * 421 |
||
61 * 3361 * 4021</pre> |
61 * 3361 * 4021</pre> |
||
=={{header|Go}}== |
|||
<lang go>package main |
|||
import "fmt" |
|||
// Use this rather than % for negative integers |
|||
func mod(n, m int) int { |
|||
return ((n % m) + m) % m |
|||
} |
|||
func isPrime(n int) bool { |
|||
if n < 2 { return false } |
|||
if n % 2 == 0 { return n == 2 } |
|||
if n % 3 == 0 { return n == 3 } |
|||
d := 5 |
|||
for d * d <= n { |
|||
if n % d == 0 { return false } |
|||
d += 2 |
|||
if n % d == 0 { return false } |
|||
d += 4 |
|||
} |
|||
return true |
|||
} |
|||
func carmichael(p1 int) { |
|||
for h3 := 2; h3 < p1; h3++ { |
|||
for d := 1; d < h3 + p1; d++ { |
|||
if (h3 + p1) * (p1 - 1) % d == 0 && mod(-p1 * p1, h3) == d % h3 { |
|||
p2 := 1 + (p1 - 1) * (h3 + p1) / d |
|||
if !isPrime(p2) { continue } |
|||
p3 := 1 + p1 * p2 / h3 |
|||
if !isPrime(p3) { continue } |
|||
if p2 * p3 % (p1 - 1) != 1 { continue } |
|||
c := p1 * p2 * p3 |
|||
fmt.Printf("%2d %4d %5d %d\n", p1, p2, p3, c) |
|||
} |
|||
} |
|||
} |
|||
} |
|||
func main() { |
|||
fmt.Println("The following are Carmichael munbers for p1 <= 61:\n") |
|||
fmt.Println("p1 p2 p3 product") |
|||
fmt.Println("== == == =======") |
|||
for p1 := 2; p1 <= 61; p1++ { |
|||
if isPrime(p1) { carmichael(p1) } |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<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> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |