Modified Sieve of Eratosthenes has very long runtime

Question

I am slowly moving through Project Euler, and have reached problem #10:

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

Find the sum of all the primes below two million.

I did a naive implementation first, which was very slow (15+ minutes runtime). But since I know the last number in the series, the Sieve of Eratosthenes should be far swifter, yet I still find it very slow. I'm wondering whether I've mis-implemented a list somewhere so I go through it far more than I should.

Assuming I haven't messed up with the list, is there some other thing that might be the slow-down, or is this just a very intensive task that should take a long time?

#include <list>
#include <iterator>
#include <iostream>


int main(){

    std::list<long long> candidates;

    candidates.begin();

    for(long long i = 2; i<2000000; i++){

        candidates.push_back(i);
    }



    long long sieve      = 0;
    long long runningSum = 0;
    long long lastSieve  = 1415;

    std::list<long long>::iterator outer = candidates.begin();
    std::list<long long>::iterator inner = candidates.begin();

    while(outer != candidates.end()){

    sieve = *outer;
    outer++;
    inner = outer;

        while(sieve < lastSieve){

            if( *inner % sieve == 0){
                inner = candidates.erase(inner);
            }
            else{
                inner++;
            }
        }
    }


    for(std::list<long long>::iterator output = candidates.begin(); output != candidates.end(); output++){

    runningSum += *output;
    }

    std::cout << "\nTotal: " << runningSum << std::endl;
    return 0;
}

Answer 1

First of all some stylistic remarks:

Unnecessary vertical whitespace

You have many empty lines that don't improve readability (and actually hurt because the reader needs to do more scrolling)

Inconsistent indentation

You need to stick to one indentation style and not switch between several. Make sure to always use the same depth of indentation.

This facilitates faster parsing of the code's structure while reading it.

Use C++11

While it might not be available to you or scares you of because of the many new features, I can only advice you to use the improvements that came with C++11.

Foremost you should go for the auto keyword and range based for loops. The latter gives a much stronger hint at what a loop iterates:

for(std::list<long long>::iterator output = candidates.begin(); output != candidates.end(); output++){

    runningSum += *output;
    }

becomes

for(auto output : candidates) {
    runningSum += output;
}

Use standard algorithms

There are several instances in your code where you reimplemented standard algorithms to some extent:

The last loop could be replaced by:

long long runningSum += std::accumulate(candidates.begin(), candidates.end(), 0);

Performance

The first thing anyone should do regarding performance problems is profiling. Most of the time our guesses about what is slow are actually wrong.

Yet, I want to give some pointers on what could be hindering performance:

• std::list provides poor cache locality, especially when it has been thinned out very much (and especially when it is so big as yours)
• the original sieve works via scattering not gathering: in your algorithm each number in the list (after the current prime) has to be tested against each sieve value in the original there is no testing but only striking out values that are multiples of the current prime

Usually prime sieving is done with an array like interface that allows to strike out elements via random access. I am keen to know why you have chosen a list instead.

Random remarks

What is the line

candidates.begin();

good for?

Why is the value of lastSieve hardcoded? You should calculate it from the size of the sieve itself.

Your variables are declared too early:

• runningSum is only needed at the end
• sieve can be declared locally in the while loop
• inner can be declared locally in the while loop

This hints at a more fundamental problem of your code:

Use more functions

Some parts of your code could gain from functions that give names to what you are doing there.

The inner while loop could be moved into a function removeMultiples.

Your whole problem code should be wrapped into a function to be reused later on (hint: project euler will require efficient prime calculation later on!)

Answer 2

I'll skip style, since you've already received very good advice on how to improve that.

The classical implementation of the sieve is that you compute multiple of each prime via addition. That is, each multiple of sieve is simply the previous multiple plus sieve. For humans using pencil and paper this is much faster than testing every number for divisibility. I think this is true for computers as well, so by using a classical implementation (and getting rid of % sieve) you can get a significant speedup.

Another common optimization is that you don't even need to find all the multiples of each prime; you only really need to find the multiples that aren't multiples of other primes you've already checked. In practice, that lets us eliminate about half the computation by looking at only the odd multiples of each prime (by adding 2*sieve each time instead of adding just sieve). We can eliminate about one-third of the remaining computation by looking only at multiples that aren't also multiples of three. (To do that, you can unroll the loop a bit so you alternately add 4*sieve and then 2*sieve.) The relevant code could look something like this, where p is the number you've just determined to be prime:

int two_p  = 2 * p;
int four_p = 4 * p;
int m = p * p;
isPrime[m] = false;
if (p % 6 == 1) {
    m += four_p;
    if (m < upperLimit) {
        isPrime[m] = false;
    }
}
m += two_p;
while (m < upperLimit) {
    isPrime[m] = false;
    m += four_p;
    if (m < upperLimit) {
        isPrime[m] = false;
    }
    m += two_p;
}

If you're clever you can eliminate a couple of those ifs, but I think a modern pipelined processor will guess the correct branch almost all the time, so those ifs may not make an appreciable difference. You could extend this technique to multiples of 5*p, 7*p, and so forth, but at some point (maybe even at 3*p) the speedup will not reward you enough to justify the added complexity of the code.

If you do use the code above, by the way, either do a preliminary loop to eliminate all multiples of 3, or make sure that when you add up the primes at the end you use a similar trick to skip all the multiples of 3 that the code above skipped. (And of course don't add any even numbers greater than 2 to your sum, but that's easy to ensure.)

Erasing an element of an std::list modifies two locations in memory rather than just one. You could presumably modify the code in your question to use a singly-linked list; but again, the classical implementation (especially for pencil and paper) is to have an array with a position for each number and mark the positions that turn out not to be prime. If you follow the advice in the previous paragraphs, you'll quickly find that it's not worth trying to use a linked list to implement those ideas even if it didn't cause any increase in running time (which I think it inevitably would).

Answer 3

Using a new boolean array produces very fast result for a Sieve of Eratosthenes. Here's an example that calulates all the primes and does the sum. Not changing the collection and only changing an elements' values increases the efficiency tremendously:

long long SumESieve(int upperLimit)
{
    int sieveBound = (int)(upperLimit - 1);
    int upperSqrt = (int)((sqrt((double)upperLimit)));
    bool* PrimeBits = new bool[upperLimit];
    memset((void*)PrimeBits, true, upperLimit * sizeof(bool));
    long long total = 2;
    for (int i = 3; i < upperSqrt; i += 2)
    {
        if (PrimeBits[i])
        {
            int step = i * 2;
            for (int j = i * i; j <= sieveBound; j += step)
            {
                PrimeBits[j] = false;
            }
            total += i;
        }
    }
    if (upperSqrt++ % 2 == 1)
        upperSqrt++;
    for (int i = upperSqrt; i < sieveBound; i += 2)
    {
        if (PrimeBits[i])
        {
            total += i;
        }
    }
    delete PrimeBits;
    return total;
}

Since the purpose is to get the sum, this starts with a the total set to 2. The outer loop only needs to check the odd numbers and the inner loop only needs to set the odd multiples of the prime.