Please implement a function in C++ that computes all primes up to a given input number,…
- User
Please implement a function in C++ that computes all primes up to a given input number, using the sieve of Eratosthenes.
Assistant
Sure, here's an implementation of the Sieve of Eratosthenes in C++ to find all the prime numbers up to a given input number:
#include <bits/stdc++.h> using namespace std; vector<int> sieveOfEratosthenes(int n) { vector<bool> isComposite(n+1, false); vector<int> primes; for (int i = 2; i*i <= n; i++) { if (!isComposite[i]) { for (int j = i*i; j <= n; j += i) { isComposite[j] = true; } } } for (int i = 2; i <= n; i++) { if (!isComposite[i]) { primes.push_back(i); } } return primes; } int main() { int n = 30; vector<int> primes = sieveOfEratosthenes(n); for (int i = 0; i < primes.size(); i++) { cout << primes[i] << " "; } return 0; }In this implementation, we use a boolean vector
isCompositeto mark the composite numbers. ThesieveOfEratosthenesfunction takes an integernas input, which represents the maximum number to check for primes. The function initializes theisCompositevector withfalsevalues for all indices up ton.The function then iterates through all numbers from 2 to the square root of
n(since all factors of a composite number must be less than or equal to its square root). If a number is not marked as composite, it is a prime, and the function marks all of its multiples as composite by setting the corresponding values in theisCompositevector totrue.Finally, the function iterates through all numbers from 2 to
nand adds the prime numbers to a vector calledprimes. This vector is returned as the
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.