Sequence of primorial primes: Difference between revisions

Content added Content deleted

Inline

@@ Line 98: / Line 98: @@
 #include <iostream>
 #include <sstream>
-#include <vector>
 #include <gmpxx.h>
+#include "sieve_of_eratosthenes.h"
 typedef mpz_class integer;
-void find_primes(std::vector<bool>& isprime, size_t limit)
-{
-    isprime.assign(limit, true);
-    isprime[0] = isprime[1] = false;
-    for (size_t p = 2; p * p < limit; ++p)
-    {
-        if (isprime[p])
-        {
-            for (size_t i = p * p; i < limit; i += p)
-                isprime[i] = false;
-        }
-    }
-}
 bool is_prime(const integer& n)
@@ Line 127: / Line 113: @@
     const size_t max = 20;
+    sieve_of_eratosthenes sieve(max_prime);
-    std::vector<bool> isprime;
-    find_primes(isprime, max_prime);
     integer primorial = 1;
     for (size_t p = 0, count = 0, index = 0; p < max_prime && count < max; ++p)
     {
-        if (!isprime[p])
+        if (!sieve.is_prime(p))
             continue;
         primorial *= p;
@@ Line 149: / Line 134: @@
     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}}