User:Simonjsaunders/Prime sieve

Implementations of the Sieve of Eratosthenes used in some of my task solutions.

C++

<lang cpp>#ifndef PRIME_SIEVE_HPP

1. define PRIME_SIEVE_HPP

1. include <vector>

/**

* A simple implementation of the Sieve of Eratosthenes.
* See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
*/

class prime_sieve { public:

   explicit prime_sieve(size_t);
   bool is_prime(size_t) const;

private:

   std::vector<bool> is_prime_;

};

/**

* Constructs a sieve with the given limit.
*
* @param limit the maximum integer that can be tested for primality
*/

inline prime_sieve::prime_sieve(size_t limit) {

   is_prime_.resize(limit/2, true);
   for (size_t p = 3; p * p <= limit; p += 2) {
       if (is_prime_[p/2 - 1]) {
           size_t inc = 2 * p;
           for (size_t q = p * p; q <= limit; q += inc)
               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 prime_sieve::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);

}

1. endif</lang>