Modified Sieve of Eratosthenes has very long runtime

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 
#include 
#include 

int main(){

    std::list candidates;

    candidates.begin();

    for(long long i = 2; i::iterator outer = candidates.begin();
    std::list::iterator inner = candidates.begin();

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

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

        while(sieve ::iterator output = candidates.begin(); output != candidates.end(); output++){

    runningSum += *output;
    }

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

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::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!)

StackExchange Code Review Q#57168, answer score: 8