# 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 <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;
}

• There are already many prime sieves in C++ on this site. Your should check them out. (1) Prime Gen (2) under 2M (3) prime gen optimized (4) prime bottle neck (5) prime test (6) Last one – Martin York Jul 16 '14 at 7:55
• Well yes, obviously, and if (for some reason) I needed to factor primes for a real task, I'd use somebody else's fine-tuned algorithm. I asked here because I wanted to know why mine might be slow. – medivh Dec 16 '14 at 9:20

## 3 Answers

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

• "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." Specifically because I remove those that are struck out. If I had implemented it in an array (Or a std::vector which was my first approach), removing an element would require the copying of the entire array. – medivh Jul 16 '14 at 9:07
• @medivh: yes that is true but the cost of using a non random access container is that you have to resort to gathering which might be slower (but as I said you should measure that). It also is customary to not store numbers in the array but instead store true and false to indicate if the number with the index of this location is (possibly) prime or not. The non prime numbers are not removed in this case (you should take a look at the links in Loki Astari's comment). – Nobody moving away from SE Jul 16 '14 at 9:10

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

• "prime multiples" no such thing. this wording is a bit off. :) – Will Ness Jul 22 '14 at 17:31
• the fixing of links is only a small part of the story: the key to the sieve's efficiency is its conflation of address and value which is destroyed if elements are actually removed - forcing us to search for, and compare, the values in O(n) time, instead of using the value as address directly, i.e. in O(1) time. – Will Ness Jul 22 '14 at 17:56
• "Prime multiples" was obviously wrong (and inconsistent with the given examples); that's fixed. In a linked-list implementation you could do the entire sieving of a single prime in one pass over the list, so O(n) time for each multiple of the prime is overly pessimistic; but the implementation is far more complicated than with the array. – David K Jul 22 '14 at 19:07
• right; but the point is the comparing of values, not links fixing - that is very cheap, exactly because it's a linked list. How to do your approach efficiently is also not an obvious task - it is easy to do in O(n^1.5) (perhaps even O(n^1.5 log n)) fashion overall (when restarting from the top for each prime's multiples), and it's harder to achieve the optimal O(n (log n)^2 log (log n)) (i.e. there's an extra log n factor there). With direct access of course we easily get O(n log n log (log n)), in n primes produced (since N ~ n log n). – Will Ness Jul 22 '14 at 19:21
• The statement in the answer about "links fixing" referred to the original implementation. I had already assumed the first step of reimplementation was to ditch the linked list, since an array-like structure is the obvious choice. So we're arguing a hypothetical here. But unlike in the OP's algorithm, for a "classical" algorithm we might have to traverse several links before finding the next multiple of the current prime. It's plausible this will increase the asymptotic running time, but that implementation is so mismatched that I haven't thought about it much. – David K Jul 22 '14 at 19:53

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.

• won't this code fail on 32-bit int platforms? (in 2 places) – Will Ness Jul 22 '14 at 10:09
• @WillNess - Change the total variable and the return type to long and it should work. – tinstaafl Jul 22 '14 at 16:34
• you meant long long (yes, the problem was only in 1 place, I misread the code). BTW why the - 1 in upperSqrt definition? Why not + 1 or just nothing? (e.g. upperLimit==26 ... ). -- Also, you don't mark any even numbers, which is good, but they still take up the place in the array... – Will Ness Jul 22 '14 at 18:09
• I tried to optimized this for the specific problem, which is to get the sum not create a list of primes. – tinstaafl Jul 22 '14 at 18:27
• but your - 1 seems to just be wrong (e.g. consider upperLimit==26 ... I doubt that you get the correct result with this code). and saving twice as much space is equally valid an optimization for calculating sum as well as for anything else (though yes, for primes under just 2000000 it doesn't matter). – Will Ness Jul 22 '14 at 18:48