85 lines
1.4 KiB
C++
85 lines
1.4 KiB
C++
/*
|
|
* Project Euler Solutions - Shared Utilities Module
|
|
* -----------------------------------------------
|
|
* File : sieve.hpp
|
|
*
|
|
* Author : erick-alcachofa
|
|
* Created : Monday, August 04 2025
|
|
*
|
|
* Notes:
|
|
* - Utility Eratosthenes sieve class
|
|
*
|
|
* License : GNU Affero General Public License v3.0 (AGPLv3)
|
|
* https://www.gnu.org/licenses/agpl-3.0.html
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
#include <vector>
|
|
#include <cstdio>
|
|
|
|
struct SieveAutoFill{};
|
|
|
|
template <std::integral T>
|
|
struct Sieve {
|
|
Sieve(T MaxPrime)
|
|
: MaxPrime(MaxPrime)
|
|
, isPrime(MaxPrime + 1, true) { }
|
|
|
|
Sieve(T MaxPrime, SieveAutoFill)
|
|
: MaxPrime(MaxPrime)
|
|
, isPrime(MaxPrime + 1, true) {
|
|
Fill();
|
|
}
|
|
|
|
~Sieve() = default;
|
|
|
|
void Fill() {
|
|
isPrime[0] = false;
|
|
isPrime[1] = false;
|
|
|
|
for (T p = 2; p <= MaxPrime; ++p) {
|
|
if (isPrime[p]) {
|
|
primes.push_back(p);
|
|
|
|
for (T i = p * p; i <= MaxPrime; i += p) {
|
|
isPrime[i] = false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
size_t Count() const {
|
|
return primes.size();
|
|
}
|
|
|
|
T Prime(size_t idx) const {
|
|
return primes.at(idx);
|
|
}
|
|
|
|
bool IsPrime(T p) {
|
|
return isPrime.at(p);
|
|
}
|
|
|
|
auto begin() {
|
|
return primes.begin();
|
|
}
|
|
|
|
auto end() {
|
|
return primes.end();
|
|
}
|
|
|
|
auto rbegin() {
|
|
return primes.rbegin();
|
|
}
|
|
|
|
auto rend() {
|
|
return primes.rend();
|
|
}
|
|
|
|
private:
|
|
T MaxPrime;
|
|
std::vector<T> primes;
|
|
std::vector<bool> isPrime;
|
|
};
|