Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 1,719: | Line 1,719: | ||
p2, 1 + Floor[p1 p2/h3]}], {p1_, p2_, p3_} /; |
p2, 1 + Floor[p1 p2/h3]}], {p1_, p2_, p3_} /; |
||
Mod[p2 p3, p1 - 1] == 1 :> Print[p1, "*", p2, "*", p3]]</lang> |
Mod[p2 p3, p1 - 1] == 1 :> Print[p1, "*", p2, "*", p3]]</lang> |
||
=={{header|Nim}}== |
|||
{{trans|Vala}} |
|||
<lang nim>import strformat |
|||
func myMod(n, m: int64): int64 = |
|||
((n mod m) + m) mod m |
|||
func isPrime(n: int64): bool = |
|||
if n == 2 or n == 3: |
|||
return true |
|||
elif n < 2 or n mod 2 == 0 or n mod 3 == 0: |
|||
return false |
|||
var `div` = 5i64 |
|||
var `inc` = 2i64 |
|||
while `div` * `div` <= n: |
|||
`div` += `inc` |
|||
`inc` = 6 - `inc` |
|||
if n mod `div` == 0: |
|||
return false |
|||
return true |
|||
for p in 2i64..63: |
|||
if isPrime(p): |
|||
continue |
|||
for h3 in 2i64..p: |
|||
var g = h3 + p |
|||
for d in 1..g: |
|||
if g * (p - 1) mod d != 0 or myMod(-p * p, h3) != d mod h3: |
|||
continue |
|||
var q = 1 + (p - 1) * g div d |
|||
if isPrime(q): |
|||
continue |
|||
var r = 1 + (p * q div h3) |
|||
if not isPrime(r) or (q * r) mod (p - 1) != 1: |
|||
continue |
|||
echo &"{p:5} × {q:5} × {r:5} = {p * q * r:10}"</lang> |
|||
{{out}} |
|||
<pre> |
|||
9 × 9 × 41 = 3321 |
|||
9 × 9 × 17 = 1377 |
|||
15 × 15 × 113 = 25425 |
|||
15 × 15 × 29 = 6525 |
|||
21 × 93 × 977 = 1908081 |
|||
21 × 21 × 41 = 18081 |
|||
27 × 27 × 365 = 266085 |
|||
27 × 27 × 53 = 38637 |
|||
27 × 573 × 911 = 14094081 |
|||
33 × 161 × 2657 = 14116641 |
|||
33 × 33 × 545 = 593505 |
|||
33 × 33 × 65 = 70785 |
|||
35 × 35 × 613 = 750925 |
|||
35 × 35 × 409 = 501025 |
|||
35 × 35 × 307 = 376075 |
|||
35 × 35 × 205 = 251125 |
|||
35 × 35 × 137 = 167825 |
|||
35 × 35 × 103 = 126175 |
|||
39 × 39 × 761 = 1157481 |
|||
39 × 39 × 305 = 463905 |
|||
39 × 39 × 191 = 290511 |
|||
45 × 45 × 1013 = 2051325 |
|||
45 × 45 × 89 = 180225 |
|||
49 × 49 × 1201 = 2883601 |
|||
49 × 649 × 6361 = 202286161 |
|||
49 × 289 × 2833 = 40118113 |
|||
49 × 49 × 241 = 578641 |
|||
49 × 361 × 1609 = 28461601 |
|||
49 × 209 × 641 = 6564481 |
|||
49 × 49 × 97 = 232897 |
|||
49 × 1825 × 3313 = 296265025 |
|||
51 × 2651 × 67601 = 9139722801 |
|||
51 × 51 × 1301 = 3383901 |
|||
51 × 51 × 101 = 262701 |
|||
51 × 201 × 251 = 2573001 |
|||
55 × 343 × 9433 = 177953545 |
|||
55 × 55 × 757 = 2289925 |
|||
55 × 55 × 433 = 1309825 |
|||
55 × 55 × 379 = 1146475 |
|||
55 × 217 × 919 = 10968265 |
|||
55 × 55 × 109 = 329725 |
|||
57 × 57 × 113 = 367137 |
|||
57 × 5993 × 6833 = 2334159633 |
|||
63 × 63 × 1985 = 7878465 |
|||
63 × 63 × 125 = 496125 |
|||
</pre> |
|||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |