# User:Simonjsaunders/Prime sieve

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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>