Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
m (→optimized: added another output section.) |
(→{{header|Java}}: added Java) |
||
Line 452: | Line 452: | ||
-> |
-> |
||
</pre> |
</pre> |
||
=={{header|Java}}== |
|||
{{trans|D}} |
|||
<lang java>public class Test { |
|||
static int mod(int n, int m) { |
|||
return ((n % m) + m) % m; |
|||
} |
|||
static boolean isPrime(int n) { |
|||
if (n == 2 || n == 3) |
|||
return true; |
|||
else if (n < 2 || n % 2 == 0 || n % 3 == 0) |
|||
return false; |
|||
for (int div = 5, inc = 2; Math.pow(div, 2) <= n; |
|||
div += inc, inc = 6 - inc) |
|||
if (n % div == 0) |
|||
return false; |
|||
return true; |
|||
} |
|||
public static void main(String[] args) { |
|||
for (int p = 2; p < 62; p++) { |
|||
if (!isPrime(p)) |
|||
continue; |
|||
for (int h3 = 2; h3 < p; h3++) { |
|||
int g = h3 + p; |
|||
for (int d = 1; d < g; d++) { |
|||
if ((g * (p - 1)) % d != 0 || mod(-p * p, h3) != d % h3) |
|||
continue; |
|||
int q = 1 + (p - 1) * g / d; |
|||
if (!isPrime(q)) |
|||
continue; |
|||
int r = 1 + (p * q / h3); |
|||
if (!isPrime(r) || (q * r) % (p - 1) != 1) |
|||
continue; |
|||
System.out.printf("%d x %d x %d%n", p, q, r); |
|||
} |
|||
} |
|||
} |
|||
} |
|||
}</lang> |
|||
<pre>3 x 11 x 17 |
|||
5 x 29 x 73 |
|||
5 x 17 x 29 |
|||
5 x 13 x 17 |
|||
7 x 19 x 67 |
|||
7 x 31 x 73 |
|||
7 x 13 x 31 |
|||
7 x 23 x 41 |
|||
7 x 73 x 103 |
|||
7 x 13 x 19 |
|||
13 x 61 x 397 |
|||
13 x 37 x 241 |
|||
13 x 97 x 421 |
|||
13 x 37 x 97 |
|||
13 x 37 x 61 |
|||
17 x 41 x 233 |
|||
17 x 353 x 1201 |
|||
19 x 43 x 409 |
|||
19 x 199 x 271 |
|||
23 x 199 x 353 |
|||
29 x 113 x 1093 |
|||
29 x 197 x 953 |
|||
31 x 991 x 15361 |
|||
31 x 61 x 631 |
|||
31 x 151 x 1171 |
|||
31 x 61 x 271 |
|||
31 x 61 x 211 |
|||
31 x 271 x 601 |
|||
31 x 181 x 331 |
|||
37 x 109 x 2017 |
|||
37 x 73 x 541 |
|||
37 x 613 x 1621 |
|||
37 x 73 x 181 |
|||
37 x 73 x 109 |
|||
41 x 1721 x 35281 |
|||
41 x 881 x 12041 |
|||
41 x 101 x 461 |
|||
41 x 241 x 761 |
|||
41 x 241 x 521 |
|||
41 x 73 x 137 |
|||
41 x 61 x 101 |
|||
43 x 631 x 13567 |
|||
43 x 271 x 5827 |
|||
43 x 127 x 2731 |
|||
43 x 127 x 1093 |
|||
43 x 211 x 757 |
|||
43 x 631 x 1597 |
|||
43 x 127 x 211 |
|||
43 x 211 x 337 |
|||
43 x 433 x 643 |
|||
43 x 547 x 673 |
|||
43 x 3361 x 3907 |
|||
47 x 3359 x 6073 |
|||
47 x 1151 x 1933 |
|||
47 x 3727 x 5153 |
|||
53 x 157 x 2081 |
|||
53 x 79 x 599 |
|||
53 x 157 x 521 |
|||
59 x 1451 x 2089 |
|||
61 x 421 x 12841 |
|||
61 x 181 x 5521 |
|||
61 x 1301 x 19841 |
|||
61 x 277 x 2113 |
|||
61 x 181 x 1381 |
|||
61 x 541 x 3001 |
|||
61 x 661 x 2521 |
|||
61 x 271 x 571 |
|||
61 x 241 x 421 |
|||
61 x 3361 x 4021</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |