# Project Euler Problem 10 - Sum of primes < 2mil

/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.
*/
#include <iostream>
#include <vector>

using namespace std;

int main(){
//We will be storing the primes as bool in a vector.
vector<bool>primes(2000000,true);

// This is the Sieve of Eratosthenes. It is not perfect, but It solve's the problem.

primes = 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.

Since you're writing in C++, I'd suggest making a class. Here's a class declaration:

class Sieve
{
public:
Sieve(unsigned maxval=4000000);
long long sum(unsigned val = 0) const;
unsigned primesBelow(unsigned val) const;
bool isPrime(unsigned val) const;
private:
bool clr(unsigned val) { nums[val>>1] = false; }
bool get(unsigned val) const { return nums[val>>1]; }
unsigned adjust(unsigned val) const { return (val == 0 || val > maxnum) ? maxnum : val; }
unsigned maxnum;
std::vector<bool>nums;
};


When it's implemented, you create the Sieve object once, which does the actual sieve algorithm in the constructor, and then use it as many times as needed to get multiple answers very quickly. For example:

int main()
{
const unsigned maxprime = 2000000;
Sieve sv(maxprime);
std::cout << sv.sum() << '\t' << sv.primesBelow(maxprime) << '\n';
std::cout << sv.sum(10) << '\t' << sv.primesBelow(10) << '\n';
}


This prints:

142913828922        148933
17        4


Some further optimizations are also possible above those mentioned already by others. For example, since all even numbers except 2 are composite (that is, not prime), one can write the isPrime() function this way:

bool Sieve::isPrime(unsigned val) const
{
if (val < 2 || val > maxnum)
return false;
if (val == 2)
return true;
return (val & 1) ? get(val) : false;
}


The code, as written, returns false if the number passed in is larger than the maxnum used for the constructor. Better alternative approaches include throwing an exception and automatically extending the internal array to accomodate. I'll leave it for you to implement those if you care to.

You may also wonder why I've used get(val) instead of accessing the vector directly. The reason is that because of the earlier observation that all even numbers greater than 2 are composite, there's not really any need to store them. For that reason, the private get() function is defined as

bool get(unsigned val) const { return nums[val>>1]; }


Because the contructor sets every member to true during construction, all we need to provide is a clr function rather than the more typical set() function. It's defined as

bool clr(unsigned val) { nums[val>>1] = false; }


Both of these are implemented as private because they assume that they will only be called with odd numbers less than the maximum. No error checking is done within them, so making them private means they're less likely to be improperly called.

Now the constructor, which actually implements the sieve function can put all of these optimizations to use:

Sieve::Sieve(unsigned maxval) : maxnum(maxval), nums(maxnum>>1, true)
{
unsigned limit = sqrt(maxnum);
for(unsigned a = 3; a <= limit; a+=2)
if(isPrime(a))
for(unsigned c=a+a, b=a+c; b < maxnum; b+=c)
clr(b);
}


Another optimization is here that isn't yet mentioned. In the inner loop, we could step through every multiple of a, but that's really not necessary. Since the construction of the outer loop means that a is always an odd number, a+a would be an even number and therefore already known to not be prime. All we want to check is odd numbers, so we start with a+a+a and increment by a+a ever inner loop iteration. This gives us 3*a, 5*a, 7*a, etc. which are all odd numbers and doubles the speed of that loop versus stepping through by a each time.

Another potential optimization that I didn't implement was to rewrite the constructor such that the loop variables didn't need shifting within the clr() function.

Finally, the sum function which was the point of your original program is implemented.

long long Sieve::sum(unsigned val) const
{
long long total = 0;
for(unsigned i = 1; i < val; ++i) {
total += isPrime(i) ? i : 0;
}
}


Note that an optimization not done here is to take advantage of the fact that it's not really necessary to step through all numbers when we know that other than 2, only odd numbers are prime. On my machine, this code runs fast enough that it was hard to measure the difference when I did that optimization, so I just left it as this more straightforward implementation. The nice part about defining this as a member function within a class is that the interface (and therefore all users of the code) would be unaffected by such a change.

As a bonus, if we want to know the number of primes below a certain number, it comes essentiall "for free" because the sieve has already done the hard part.

unsigned Sieve::primesBelow(unsigned val) const
{
unsigned count = 0;
for (unsigned i = 1; i < val; ++i)
count += isPrime(i) ? 1 : 0;
return count;
}


The potential problem with both of these is that they adjust() their incoming argument to a value within range. This is probably not the best solution and the same discussion about remedies for isPrime() apply here, too.

On my machine this code ran about 4 times faster that the original code and takes a vector half as long. It's also adjustable at runtime, avoiding the inflexibility of hard-coding a constant like 2000000.

Edit: One other thing I should have mentioned: Please don't get into the habit of using namespace std in your code because it reintroduces the name collision problem that namespaces were introduced to solve! See this StackOverflow question for further info on that topic.

• I've tried to avoid using namespace std. I can't recall why I did here. I had a hard time understanding classes till I read this, and it really helped. I don't think I can replicate it on my own yet though. – Twooey Apr 11 '14 at 1:48
• You introduce this optimization but didn't call it out AFAICT: by checking isPrime(x * y) in the sieve, you avoid knocking out multiples of x * y since you've already knocked out those of x. This pays off in spades with large ranges. – David Harkness Apr 11 '14 at 3:05

• 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<bool> 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 a*a+b*a 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.

// 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.

• Agree in general; the next logical step would be renaming primes to is_prime. – vnp Apr 10 '14 at 21:14
• @user58697: That is also good. – Jamal Apr 10 '14 at 21:18

There are three relatively simple improvements you can make, that should be relatively trivial to implement.

1. treat 2 as a special prime:

• Change initializer of total:

long long total = 2;

• Change step in for loop (start at 3, increment by 2):

for(int a = 3; a*a < primes.size(); a+=2){

• have a special case for if the desired sum is for primes less than 2.... but this is the main method, and the value is a constant, so unnecessary.

2. precompute the sqrt of primes.size():

• initialize it:

int limit = (int)sqrt(primes.size());

• and use this as the limit in the loop:

for(int a = 3; a <= limit; a+=2){

3. include the total addition inside the prime loop:

 long long total = 2;
int limit = (int)sqrt(primes.size());
for(int a = 3; a<=limit; a+=2){
if(primes[a]==true){
total += a;
.......


then there is no need for the second loop.