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