75 lines
1.9 KiB
C++
75 lines
1.9 KiB
C++
|
#include <iostream>
|
||
|
|
#include <string>
|
||
|
|
#include <vector>
|
||
|
|
|
||
|
|
class Sieve {
|
||
|
|
private:
|
||
|
|
std::string sieve;
|
||
|
|
|
||
|
|
public:
|
||
|
|
// Constructor to initialize sieve with 'P' (prime assumption)
|
||
|
|
Sieve(size_t limit) : sieve(limit + 1, 'P') {
|
||
|
|
// 0 and 1 are not primes
|
||
|
|
sieve[0] = 'C';
|
||
|
|
if (limit > 0) sieve[1] = 'C';
|
||
|
|
|
||
|
|
// Sieve of Eratosthenes
|
||
|
|
for (size_t i = 2; i * i <= limit; ++i) {
|
||
|
|
if (sieve[i] == 'P') {
|
||
|
|
for (size_t j = i * i; j <= limit; j += i) {
|
||
|
|
sieve[j] = 'C';
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Get primes as a vector of integers
|
||
|
|
std::vector<int> getPrimes() const {
|
||
|
|
std::vector<int> primes;
|
||
|
|
for (size_t i = 2; i < sieve.size(); ++i) {
|
||
|
|
if (sieve[i] == 'P') {
|
||
|
|
primes.push_back(i);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return primes;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Print all primes in the range
|
||
|
|
void printPrimesInRange(int start, int end) const {
|
||
|
|
for (int i = start; i <= end; ++i) {
|
||
|
|
if (sieve[i] == 'P') {
|
||
|
|
std::cout << i << " ";
|
||
|
|
}
|
||
|
|
}
|
||
|
|
std::cout << std::endl;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Get the largest prime below a limit
|
||
|
|
int largestPrimeBelow(int limit) const {
|
||
|
|
for (int i = limit; i >= 2; --i) {
|
||
|
|
if (sieve[i] == 'P') {
|
||
|
|
return i;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return -1; // If no prime is found
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
// Main function for testing
|
||
|
|
int main() {
|
||
|
|
const int limit = 100000;
|
||
|
|
|
||
|
|
// Create a Sieve instance for the range 0 to limit
|
||
|
|
Sieve sieve(limit);
|
||
|
|
|
||
|
|
// Print primes between 1 and 200
|
||
|
|
std::cout << "Primes between 1 and 200:" << std::endl;
|
||
|
|
sieve.printPrimesInRange(1, 200);
|
||
|
|
|
||
|
|
// Find and print the largest prime below 100,000
|
||
|
|
int largestPrime = sieve.largestPrimeBelow(limit);
|
||
|
|
std::cout << "Largest prime below " << limit << ": " << largestPrime << std::endl;
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|