Chernick's Carmichael numbers: Difference between revisions

Content added Content deleted

Inline

@@ Line 52: / Line 52: @@
 <br><br>
+=={{header|C++}}==
+<lang cpp>#include <gmp.h>
+#include <iostream>
+using namespace std;
+typedef unsigned long long int u64;
+bool primality_pretest(u64 k) {     // for k > 23
+    if (!(k %  3) || !(k %  5) || !(k %  7) || !(k % 11) ||
+        !(k % 13) || !(k % 17) || !(k % 19) || !(k % 23)
+    ) {
+        return (k <= 23);
+    }
+    return true;
+}
+bool probprime(u64 k, mpz_t n) {
+    mpz_set_ui(n, k);
+    return mpz_probab_prime_p(n, 0);
+}
+bool is_chernick(int n, u64 m, mpz_t z) {
+    if (!primality_pretest(6 * m + 1)) {
+        return false;
+    }
+    if (!primality_pretest(12 * m + 1)) {
+        return false;
+    }
+    if (!primality_pretest(18 * m + 1)) {
+        return false;
+    }
+    u64 t = 9 * m;
+    for (int i = 2; i <= n - 2; i++) {
+        if (!primality_pretest((t << i) + 1)) {
+            return false;
+        }
+    }
+    if (!probprime(6 * m + 1, z)) {
+        return false;
+    }
+    if (!probprime(12 * m + 1, z)) {
+        return false;
+    }
+    if (!probprime(18 * m + 1, z)) {
+        return false;
+    }
+    for (int i = 2; i <= n - 2; i++) {
+        if (!probprime((t << i) + 1, z)) {
+            return false;
+        }
+    }
+    return true;
+}
+int main() {
+    mpz_t z;
+    mpz_inits(z, NULL);
+    for (int n = 3; n <= 10; n++) {
+        // `m` is a multiple of 2^(n-4), for n > 4
+        u64 multiplier = (n > 4) ? (1 << (n - 4)) : 1;
+        // For n > 5, m is also a multiple of 5
+        if (n > 5) {
+            multiplier *= 5;
+        }
+        for (u64 k = 1; ; k++) {
+            u64 m = k * multiplier;
+            if (is_chernick(n, m, z)) {
+                cout << "a(" << n << ") has m = " << m << endl;
+                break;
+            }
+        }
+    }
+    return 0;
+}</lang>
+{{out}}
+<pre>
+a(3) has m = 1
+a(4) has m = 1
+a(5) has m = 380
+a(6) has m = 380
+a(7) has m = 780320
+a(8) has m = 950560
+a(9) has m = 950560
+a(10) has m = 3208386195840
+</pre>
+(takes ~3.5 minutes)
 =={{header|F_Sharp|F#}}==
 This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]