patterncppModerate
Project Euler Problem 10 - Sum of primes < 2mil
Viewed 0 times
problemprimesprojecteulersum2mil
Problem
/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
*/
#include
#include
using namespace std;
int main(){
//We will be storing the primes as bool in a vector.
vectorprimes(2000000,true);
// This is the Sieve of Eratosthenes. It is not perfect, but It solve's the problem.
primes[1] = false;
for(int a = 2; a*a < primes.size(); ++a){
if(primes[a]==true){
for(int b = 0; a*a+b*a < primes.size(); ++b){
primes[a*a+b*a] = false;
}
}
}
//This simply add's all the prime numbers
long long total = 0;
for(int c = 1; c < primes.size(); c++){
if(primes[c] == true)
total +=c;
}
std::cout << total;
return 0;
}This works well. I'm trying to improve my C++ and was wondering if there is a way to improve on it. I'm just learning, and would welcome any advice.
Solution
I have several things to add onto @rolfl's great advice:
-
Since you have a container of
-
I might still assign the
You could have something like this (feel free to use a better name):
-
You can leave out the
This
is the same as
If you were to do something with
-
You're hard-coding
You could assign it to a local variable and use it where it's needed. To keep it within a close scope (it's only needed within a small space), initialize it within the loop.
-
Some of your comments seem noisy/useless:
The "we" sounds like you're demonstrating this code for a tutorial or such, and this doesn't appear to be the intent. Just a simple "this does..." or "this is..." will do.
Other than that, the entire comment is not helpful. It's clear that it's an
The second sentence is just noisy and adds nothing of value; just remove it. The first sentence, however, is okay because it's not entirely obvious that this is the Sieve.
-
Since you have a container of
bools, which doesn't store the actual primes, consider renaming primes to is_prime or something similar. This sounds more conditional and makes more sense with the type of values being stored.-
I might still assign the
2000000 to a constant to make this more understandable for users without the full documentation (someone might otherwise think that there should be 2M primes, looking at the vector's name). It would also help in case you'll need this number elsewhere.You could have something like this (feel free to use a better name):
const int maxNumbers = 2000000;
std::vector primes(maxNumbers, true);-
You can leave out the
true from your if statements:This
if(primes[a]==true)is the same as
if(primes[a])If you were to do something with
false, you would use !:if(!primes[a])-
You're hard-coding
aa+ba in some places, and it's not quite clear what this computation corresponds to (especially with your single-character variable names).You could assign it to a local variable and use it where it's needed. To keep it within a close scope (it's only needed within a small space), initialize it within the loop.
-
Some of your comments seem noisy/useless:
// We will be storing the primes as bool in a vector.The "we" sounds like you're demonstrating this code for a tutorial or such, and this doesn't appear to be the intent. Just a simple "this does..." or "this is..." will do.
Other than that, the entire comment is not helpful. It's clear that it's an
std::vector of bools that stores primes. There's no need to state the obvious; the code speaks for itself.// This is the Sieve of Eratosthenes. It is not perfect, but It solve's the problem.The second sentence is just noisy and adds nothing of value; just remove it. The first sentence, however, is okay because it's not entirely obvious that this is the Sieve.
Code Snippets
const int maxNumbers = 2000000;
std::vector<bool> primes(maxNumbers, true);if(primes[a]==true)if(primes[a])if(!primes[a])// We will be storing the primes as bool in a vector.Context
StackExchange Code Review Q#46835, answer score: 14
Revisions (0)
No revisions yet.