Ormiston pairs: Difference between revisions

Content added Content deleted

Inline

@@ Line 116: / Line 116: @@
 =={{header|C++}}==
+{{libheader|Primesieve}}
 <syntaxhighlight lang="cpp">#include <algorithm>
-#include <cassert>
 #include <iomanip>
 #include <iostream>
-#include <vector>
+#include <utility>
+#include <primesieve.hpp>
-std::vector<bool> prime_sieve(int limit) {
-    std::vector<bool> sieve(limit, true);
-    if (limit > 0)
-        sieve[0] = false;
-    if (limit > 1)
-        sieve[1] = false;
-    for (int i = 4; i < limit; i += 2)
-        sieve[i] = false;
-    for (int p = 3, sq = 9; sq < limit; p += 2) {
-        if (sieve[p]) {
-            for (int q = sq; q < limit; q += p << 1)
-                sieve[q] = false;
-        }
-        sq += (p + 1) << 2;
-    }
-    return sieve;
-}
 class digit_set {
 public:
-    explicit digit_set(int n) {
+    digit_set() {}
+    explicit digit_set(uint64_t n) {
         for (; n > 0; n /= 10)
             ++count_[n % 10];
@@ Line 153: / Line 138: @@
 private:
     int count_[10] = {};
+};
+class ormiston_pair_generator {
+public:
+    ormiston_pair_generator() { prime_ = pi_.next_prime(); }
+    std::pair<uint64_t, uint64_t> next_pair() {
+        for (;;) {
+            uint64_t prime = prime_;
+            auto digits = digits_;
+            prime_ = pi_.next_prime();
+            digits_ = digit_set(prime_);
+            if (digits_ == digits)
+                return std::make_pair(prime, prime_);
+        }
+    }
+private:
+    primesieve::iterator pi_;
+    uint64_t prime_;
+    digit_set digits_;
 };
 int main() {
+    ormiston_pair_generator generator;
-    const int limit = 100000000;
+    int count = 0;
-    std::vector<bool> sieve = prime_sieve(limit);
-    int count = 0, count1 = 0, count2 = 0;
     std::cout << "First 30 Ormiston pairs:\n";
-    for (int p1 = 0, p2 = 0; p2 < limit; ++p2) {
+    for (; count < 30; ++count) {
-        if (!sieve[p2])
+        auto [p1, p2] = generator.next_pair();
+        std::cout << '(' << std::setw(5) << p1 << ", " << std::setw(5) << p2
-            continue;
+                  << ')' << ((count + 1) % 3 == 0 ? '\n' : ' ');
-        if (digit_set(p2) == digit_set(p1)) {
+    }
-            if (count1 == 0 && p2 > 1000000)
+    std::cout << '\n';
-                count1 = count;
+    for (uint64_t limit = 1000000; limit <= 1000000000; ++count) {
-            if (count2 == 0 && p2 > 10000000)
-                count2 = count;
+        auto [p1, p2] = generator.next_pair();
-            ++count;
+        if (p1 > limit) {
+            std::cout << "Number of Ormiston pairs < " << limit << ": " << count
-            if (count <= 30)
-                std::cout << '(' << std::setw(5) << p1 << ", " << std::setw(5)
+                      << '\n';
-                          << p2 << ')' << (count % 3 == 0 ? '\n' : ' ');
+            limit *= 10;
         }
-        p1 = p2;
     }
-    std::cout << "\nNumber of Ormiston pairs < 1,000,000: " << count1 << '\n';
-    std::cout << "Number of Ormiston pairs < 10,000,000: " << count2 << '\n';
-    std::cout << "Number of Ormiston pairs < 100,000,000: " << count << '\n';
 }</syntaxhighlight>
@@ Line 194: / Line 194: @@
 (75913, 75931) (76213, 76231) (76579, 76597)
-Number of Ormiston pairs < 1,000,000: 382
+Number of Ormiston pairs < 1000000: 382
-Number of Ormiston pairs < 10,000,000: 3722
+Number of Ormiston pairs < 10000000: 3722
-Number of Ormiston pairs < 100,000,000: 34901
+Number of Ormiston pairs < 100000000: 34901
+Number of Ormiston pairs < 1000000000: 326926
 </pre>