#include <iostream> // cout, endl
#include <vector> // std::vector
#include <cmath> // std::sqrt
/*
Create a list: Start with a list of consecutive integers from 2 up to the desired limit (n).
The first number in the list, 2, is a prime number.
Eliminate all multiples of 2 (4, 6, 8, etc.) from the list.
The next number in the list is 3, which is also a prime number.
Eliminate all multiples of 3 (6, 9, 12, etc.) from the list.
Continue this process, moving to the next number and eliminating its multiples, until you reach
the square root of the limit (n).
Primes remain: All the numbers that remain unmarked in the list are prime numbers.
*/
/**
* @brief Implements the Sieve of Eratosthenes to find all prime numbers up to a given limit.
*
* @param limit The upper bound (inclusive) up to which to find prime numbers.
* @return A std::vector<bool> where vector[i] is true if i is prime, false otherwise.
* The vector size will be (limit + 1).
*/
std::vector<bool> sieveOfEratosthenes(int limit) {
// 1. Create a boolean array `isPrime[0...limit]` and initialize all entries as true.
// `isPrime[i]` will be false if i is not a prime, else true.
// Initialize with true, then mark 0 and 1 as false.
std::vector<bool> isPrime(limit + 1, true);
// 0 and 1 are not prime numbers
if (limit >= 0) {
isPrime[0] = false;
}
if (limit >= 1) {
isPrime[1] = false;
}
// 2. Start with the first prime number, p = 2.
// We only need to iterate up to sqrt(limit) because any composite number 'n'
// will have at least one prime factor less than or equal to sqrt(n).
for (long long p = 2; p * p <= limit; p++) {
// If isPrime[p] is still true, then it is a prime number.
if (isPrime[p]) {
// Mark all multiples of p (starting from p*p) as not prime.
// Multiples less than p*p would have already been marked by smaller primes.
for (long long i = p * p; i <= limit; i += p) {
isPrime[i] = false;
}
}
}
return isPrime;
}
/**
* @brief Prints the prime numbers found by the sieve and their count.
*
* @param isPrime A vector<bool> indicating primality (from sieveOfEratosthenes).
*/
void printPrimes(const std::vector<bool>& isPrime) {
int count = 0;
std::cout << "Prime numbers up to " << (isPrime.size() - 1) << " are:\n";
for (int p = 2; p < isPrime.size(); ++p) {
if (isPrime[p]) {
std::cout << p << " ";
count++;
}
}
std::cout << "\nTotal primes found: " << count << std::endl;
}
int main() {
int limit;
std::cout << "Enter the upper limit to find prime numbers up to: ";
std::cin >> limit;
if (limit < 0) {
std::cerr << "Error: Limit cannot be negative.\n";
return 1;
}
// Run the Sieve algorithm
std::vector<bool> primes = sieveOfEratosthenes(limit);
// Print the results
printPrimes(primes);
}
/*
run:
Enter the upper limit to find prime numbers up to: 500
Prime numbers up to 500 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211
223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331
337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449
457 461 463 467 479 487 491 499
Total primes found: 95
*/
