Carmichael 3 strong pseudoprimes: Difference between revisions

Content added Content deleted

Inline

@@ Line 410: / Line 410: @@
 241 421
 3361 4021
+</pre>
+=={{header|C++}}==
+<lang cpp>#include <iomanip>
+#include <iostream>
+int mod(int n, int d) {
+    return (d + n % d) % d;
+}
+bool is_prime(int n) {
+    if (n < 2)
+        return false;
+    if (n % 2 == 0)
+        return n == 2;
+    if (n % 3 == 0)
+        return n == 3;
+    for (int p = 5; p * p <= n; p += 4) {
+        if (n % p == 0)
+            return false;
+        p += 2;
+        if (n % p == 0)
+            return false;
+    }
+    return true;
+}
+void print_carmichael_numbers(int prime1) {
+    for (int h3 = 1; h3 < prime1; ++h3) {
+        for (int d = 1; d < h3 + prime1; ++d) {
+            if (mod((h3 + prime1) * (prime1 - 1), d) != 0
+                || mod(-prime1 * prime1, h3) != mod(d, h3))
+                continue;
+            int prime2 = 1 + (prime1 - 1) * (h3 + prime1)/d;
+            if (!is_prime(prime2))
+                continue;
+            int prime3 = 1 + prime1 * prime2/h3;
+            if (!is_prime(prime3))
+                continue;
+            if (mod(prime2 * prime3, prime1 - 1) != 1)
+                continue;
+            unsigned int c = prime1 * prime2 * prime3;
+            std::cout << std::setw(2) << prime1 << " x "
+                << std::setw(4) << prime2 << " x "
+                << std::setw(5) << prime3 << " = "
+                << std::setw(10) << c << '\n';
+        }
+    }
+}
+int main() {
+    for (int p = 2; p <= 61; ++p) {
+        if (is_prime(p))
+            print_carmichael_numbers(p);
+    }
+    return 0;
+}</lang>
+{{out}}
+<pre style="height:50ex">
+x   11 x    17 =        561
+x   29 x    73 =      10585
+x   17 x    29 =       2465
+x   13 x    17 =       1105
+x   19 x    67 =       8911
+x   31 x    73 =      15841
+x   13 x    31 =       2821
+x   23 x    41 =       6601
+x   73 x   103 =      52633
+x   13 x    19 =       1729
+x   61 x   397 =     314821
+x   37 x   241 =     115921
+x   97 x   421 =     530881
+x   37 x    97 =      46657
+x   37 x    61 =      29341
+x   41 x   233 =     162401
+x  353 x  1201 =    7207201
+x   43 x   409 =     334153
+x  199 x   271 =    1024651
+x  199 x   353 =    1615681
+x  113 x  1093 =    3581761
+x  197 x   953 =    5444489
+x  991 x 15361 =  471905281
+x   61 x   631 =    1193221
+x  151 x  1171 =    5481451
+x   61 x   271 =     512461
+x   61 x   211 =     399001
+x  271 x   601 =    5049001
+x  181 x   331 =    1857241
+x  109 x  2017 =    8134561
+x   73 x   541 =    1461241
+x  613 x  1621 =   36765901
+x   73 x   181 =     488881
+x   73 x   109 =     294409
+x 1721 x 35281 = 2489462641
+x  881 x 12041 =  434932961
+x  101 x   461 =    1909001
+x  241 x   761 =    7519441
+x  241 x   521 =    5148001
+x   73 x   137 =     410041
+x   61 x   101 =     252601
+x  631 x 13567 =  368113411
+x  271 x  5827 =   67902031
+x  127 x  2731 =   14913991
+x  127 x  1093 =    5968873
+x  211 x   757 =    6868261
+x  631 x  1597 =   43331401
+x  127 x   211 =    1152271
+x  211 x   337 =    3057601
+x  433 x   643 =   11972017
+x  547 x   673 =   15829633
+x 3361 x  3907 =  564651361
+x 3359 x  6073 =  958762729
+x 1151 x  1933 =  104569501
+x 3727 x  5153 =  902645857
+x  157 x  2081 =   17316001
+x   79 x   599 =    2508013
+x  157 x   521 =    4335241
+x 1451 x  2089 =  178837201
+x  421 x 12841 =  329769721
+x  181 x  5521 =   60957361
+x 1301 x 19841 = 1574601601
+x  277 x  2113 =   35703361
+x  181 x  1381 =   15247621
+x  541 x  3001 =   99036001
+x  661 x  2521 =  101649241
+x  271 x   571 =    9439201
+x  241 x   421 =    6189121
+x 3361 x  4021 =  824389441
 </pre>