# | Likes | Tech tags | Title | Creator | Created date |
---|---|---|---|---|---|
1 | 0 |
2022-11-23 21:54
|
An \(O(n \log \log n)\) implementation of the sieve of Eratosthenes algorithm (\(n\) is the integer up to which we find the primes)
#include <vector>
std::vector<int> sieve_of_eratosthenes(int n) { // Finds all primes up to n
std::vector<bool> is_prime(n+1, true);
std::vector<int> result; // The found primes
is_prime[0] = false;
is_prime[1] = false;
for(int i=2; i <= n; i++) {
if(is_prime[i]) {
result.push_back(i);
for(int j=i; j <= n/i; j++) { // We do the for loop this way to prevent integer overflow for large n
is_prime[i*j] = false;
}
}
}
return result;
}
int main() {
std::vector<int> primes = sieve_of_eratosthenes(100);
return 0;
}
functions | ||
std::vector::operator[] |
en.cppreference.com | cplusplus.com |
std::vector::vector |
en.cppreference.com | cplusplus.com |
classes | ||
std::vector |
en.cppreference.com | cplusplus.com |
Implement the Sieve of Eratosthenes algorithm and use it to find all prime numbers up to some integer.