Unprimeable numbers: Difference between revisions

Content added Content deleted

Inline

@@ Line 295: / Line 295: @@
 #include <vector>
+/**
+ * A simple implementation of the Sieve of Eratosthenes.
+ * See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
+ */
 class sieve_of_eratosthenes {
 public:
@@ Line 300: / Line 304: @@
     bool is_prime(size_t) const;
 private:
-    std::vector<bool> odd_prime_;
+    std::vector<bool> is_prime_;
 };
+/**
-inline bool sieve_of_eratosthenes::is_prime(size_t n) const {
+ * Constructs a sieve with the given limit.
-    if (n == 2)
+ *
-        return true;
+ * @param limit the maximum integer that can be tested for primality
-    if (n < 2 || n % 2 == 0)
+ */
-        return false;
-    return odd_prime_[n/2 - 1];
-}
 inline sieve_of_eratosthenes::sieve_of_eratosthenes(size_t limit) {
-    limit = std::max(size_t(3), 1 + 2*(limit/2));
+    limit = std::max(size_t(3), limit);
-    odd_prime_.resize(limit/2, true);
+    is_prime_.resize(limit/2, true);
     for (size_t p = 3; p * p <= limit; p += 2) {
-        if (odd_prime_[p/2 - 1]) {
+        if (is_prime_[p/2 - 1]) {
             size_t inc = 2 * p;
             for (size_t q = p * p; q <= limit; q += inc)
-                odd_prime_[q/2 - 1] = false;
+                is_prime_[q/2 - 1] = false;
         }
     }
+}
+/**
+ * Returns true if the given integer is a prime number. The integer
+ * must be less than or equal to the limit passed to the constructor.
+ *
+ * @param n an integer less than or equal to the limit passed to the
+ * constructor
+ * @return true if the integer is prime
+ */
+inline bool sieve_of_eratosthenes::is_prime(size_t n) const {
+    if (n == 2)
+        return true;
+    if (n < 2 || n % 2 == 0)
+        return false;
+    return is_prime_.at(n/2 - 1);
 }