Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
No edit summary |
(Added zkl) |
||
Line 1,349: | Line 1,349: | ||
61 x 241 x 421 = 6189121 |
61 x 241 x 421 = 6189121 |
||
61 x 3361 x 4021 = 824389441 |
61 x 3361 x 4021 = 824389441 |
||
</pre> |
|||
=={{header|zkl}}== |
|||
Using the Miller-Rabin primality test in lib GMP. |
|||
<lang zkl>var BN=Import("zklBigNum"), bi=BN(0); // gonna recycle bi |
|||
primes:=T(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61); |
|||
var p2,p3; |
|||
cs:=[[(p1,h3,d); primes; { [2..p1 - 1] }; // list comprehension |
|||
{ [1..h3 + p1 - 1] }, |
|||
{ ((h3 + p1)*(p1 - 1)%d == 0 and ((-p1*p1):mod(_,h3) == d%h3)) },//guard |
|||
{ (p2=1 + (p1 - 1)*(h3 + p1)/d):bi.set(_).probablyPrime() },//guard |
|||
{ (p3=1 + (p1*p2/h3)):bi.set(_).probablyPrime() }, //guard |
|||
{ 1==(p2*p3)%(p1 - 1) }; //guard |
|||
{ T(p1,p2,p3) } // return list of three primes in Carmichael number |
|||
]]; |
|||
fcn mod(a,b) { m:=a%b; if(m<0) m+b else m }</lang> |
|||
<lang>cs.len().println(" Carmichael numbers found:"); |
|||
cs.pump(Console.println,fcn([(p1,p2,p3)]){ |
|||
"%2d * %4d * %5d = %d".fmt(p1,p2,p3,p1*p2*p3) });</lang> |
|||
{{out}} |
|||
<pre> |
|||
69 Carmichael numbers found: |
|||
3 * 11 * 17 = 561 |
|||
5 * 29 * 73 = 10585 |
|||
5 * 17 * 29 = 2465 |
|||
5 * 13 * 17 = 1105 |
|||
7 * 19 * 67 = 8911 |
|||
... |
|||
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> |