Truncatable primes: Difference between revisions

Content added Content deleted

Inline

@@ Line 529: / Line 529: @@
 =={{header|C++}}==
 <lang cpp>#include <iostream>
-#include <vector>
+#include "sieve_of_eratosthenes.h"
 int main()
@@ Line 536: / Line 536: @@
     // find the prime numbers up to the limit
-    std::vector<bool> isprime(limit + 1, true);
+    sieve_of_eratosthenes sieve(limit + 1);
-    isprime[0] = isprime[1] = false;
-    for (int p = 2; p * p <= limit; ++p)
-    {
-        if (isprime[p])
-        {
-            for (int i = p * p; i <= limit; i += p)
-                isprime[i] = false;
-        }
-    }
     int largest_left = 0;
     int largest_right = 0;
@@ Line 551: / Line 543: @@
     for (int p = limit; p >= 2; --p)
     {
-        if (!isprime[p])
+        if (!sieve.is_prime(p))
             continue;
         bool left_truncatable = true;
         for (int n = 10, q = p; p > n; n *= 10)
         {
-            if (!isprime[p % n] || q == p % n)
+            if (!sieve.is_prime(p % n) || q == p % n)
             {
                 left_truncatable = false;
@@ Line 572: / Line 564: @@
     for (int p = limit; p >= 2; --p)
     {
-        if (!isprime[p])
+        if (!sieve.is_prime(p))
             continue;
         bool right_truncatable = true;
         for (int q = p/10; q > 0; q /= 10)
         {
-            if (!isprime[q])
+            if (!sieve.is_prime(q))
             {
                 right_truncatable = false;
@@ Line 594: / Line 586: @@
     return 0;
 }</lang>
+Contents of sieve_of_eratosthenes.h:
+<lang cpp>#ifndef SIEVE_OF_ERATOSTHENES_H
+#define SIEVE_OF_ERATOSTHENES_H
+#include <vector>
+class sieve_of_eratosthenes
+{
+public:
+    explicit sieve_of_eratosthenes(size_t);
+    bool is_prime(size_t) const;
+private:
+    std::vector<bool> is_prime_;
+};
+inline bool sieve_of_eratosthenes::is_prime(size_t n) const
+{
+    return is_prime_[n];
+}
+inline sieve_of_eratosthenes::sieve_of_eratosthenes(size_t max)
+    : is_prime_(max, true)
+{
+    is_prime_[0] = is_prime_[1] = false;
+    for (size_t p = 2; p * p < max; ++p)
+    {
+        if (is_prime_[p])
+        {
+            for (size_t q = p * p; q < max; q +=p)
+                is_prime_[q] = false;
+        }
+    }
+}
+#endif</lang>
 {{out}}