patterncppMinor
Creating vector of primes using Sieve of Eratosthenes
Viewed 0 times
primescreatingsieveusingvectoreratosthenes
Problem
Please review my Sieve of Eratosthenes implementation.
How can I improve and make this faster?
std::vector generate(const int& n) {
std::vector input(n+1, true);
for (int i = 2; i * i primes{};
for (auto i = 1; i <= n; ++i) {
if (input[i]) {
primes.push_back(i);
}
}
return primes;
}How can I improve and make this faster?
Solution
From Wikipedia, the Sieve of Eratosthenes algorithm is:
To find all the prime numbers less than or equal to a given integer n
by Eratosthenes' method:
..., n).
4p, etc.; the p itself should not be marked).
equal this new number (which is the next prime), and repeat from
step 3.
Your algorithm does not seem right really, notably it skips the step 4 which is essential for fast operation; and there are some non-C++ idioms too
-
Do not return the std::vector; instead pass it as a reference to the function.
-
Do not pass integers as const references.
-
If n
-
The Eratosthenes sieve goes like: "for all values from 2 to sqrt(n) - if the number is a prime then mark all its multiples not prime. However all multiples less than i * i have been marked already composite by previous iterations.
-
Do not multiply the loop variables when a simple addition suffices.
-
As a simple optimization, the 2 is always in the primes as we skipped the "no values" already; thus we add it. Then we iterate only odd integers starting from 3.
Thus we get
Of course you do not need the second loop to just fill in the result vector; if the
To find all the prime numbers less than or equal to a given integer n
by Eratosthenes' method:
- Create a list of consecutive integers from 2 through n: (2, 3, 4,
..., n).
- Initially, let p equal 2, the first prime number.
- Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p,
4p, etc.; the p itself should not be marked).
- Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now
equal this new number (which is the next prime), and repeat from
step 3.
Your algorithm does not seem right really, notably it skips the step 4 which is essential for fast operation; and there are some non-C++ idioms too
-
Do not return the std::vector; instead pass it as a reference to the function.
-
Do not pass integers as const references.
-
If n
-
The Eratosthenes sieve goes like: "for all values from 2 to sqrt(n) - if the number is a prime then mark all its multiples not prime. However all multiples less than i * i have been marked already composite by previous iterations.
-
Do not multiply the loop variables when a simple addition suffices.
-
As a simple optimization, the 2 is always in the primes as we skipped the "no values" already; thus we add it. Then we iterate only odd integers starting from 3.
Thus we get
std::vector generate(int n) {
std::vector result = std::vector();
if (n input(n + 1, true);
// calculate the upper limit as the square root of
// of N. all composite numbers = 2, then add 2 here
result.push_back(2);
// and check only odd numbers here,
// no other even number can be set
for (int i = 3; i <= n; i += 2) {
if (input[i]) {
result.push_back(i);
}
}
return result;
}Of course you do not need the second loop to just fill in the result vector; if the
input[i] is true (the continue was not executed), the number is a prime and you can push_back it to the result vector there:if (! input[i]) {
// i is an already proven composite number,
// all its multiples have been
// marked not prime by all its prime factors by now.
continue;
}
// i is a prime
result.push_back(i);Code Snippets
std::vector<int> generate(int n) {
std::vector<int> result = std::vector<int>();
if (n < 2) {
return result;
}
// initialize the vector
std::vector<bool> input(n + 1, true);
// calculate the upper limit as the square root of
// of N. all composite numbers <= N must have a
// factor <= sqrt(N)
int sqrtN = (int)sqrt(n);
// iterate from 2 up to the square root of N
for (int i = 2; i <= sqrtN; i ++) {
if (! input[i]) {
// i is a proven composite number,
// all its multiples have been
// marked not prime by all its prime factors by now.
continue;
}
// as an optimization, all multiples *less* than
// the square of i are already marked, (they have
// another prime factor less than i), so we can start
// from the square which is the smallest composite
// not yet marked
for (int j = i * i; j <= n; j += i) {
input[j] = false;
}
}
// as n >= 2, then add 2 here
result.push_back(2);
// and check only odd numbers here,
// no other even number can be set
for (int i = 3; i <= n; i += 2) {
if (input[i]) {
result.push_back(i);
}
}
return result;
}if (! input[i]) {
// i is an already proven composite number,
// all its multiples have been
// marked not prime by all its prime factors by now.
continue;
}
// i is a prime
result.push_back(i);Context
StackExchange Code Review Q#70686, answer score: 5
Revisions (0)
No revisions yet.