Inspired by another question here: Sum of Prime numbers under 2 million, I decided to try and implement Eratosthenes' Sieve from scratch using the algorithm described in the article.
unsigned int CalculateSumOfPrimes(const unsigned int number) {
if(number <= 1) return 0;
if(number == 2) return 2;
std::vector<unsigned int> listOfPrimes;
CalculateListOfPrimes(listOfPrimes, number);
unsigned int sum = 0;
for(unsigned int i = 0; i < listOfPrimes.size(); ++i) {
sum += listOfPrimes.at(i);
}
return sum;
}
void CalculateListOfPrimes(std::vector<unsigned int>& container, const unsigned int number) {
if(container.size() != 0) {
std::cout << "Container must be empty!" << std::endl;
return;
}
unsigned int current_prime_check = 2;
std::vector<unsigned int> listOfNonPrimes;
while(current_prime_check < number) {
for(unsigned int i = current_prime_check; i < number; i += current_prime_check) {
if(i == current_prime_check) {
container.push_back(i);
continue;
}
if(std::find(listOfNonPrimes.begin(), listOfNonPrimes.end(), i) != listOfNonPrimes.end()) continue;
listOfNonPrimes.push_back(i);
}
++current_prime_check;
while(std::find(listOfNonPrimes.begin(), listOfNonPrimes.end(), current_prime_check) != listOfNonPrimes.end()) {
++current_prime_check;
}
}
}
Currently the major bottleneck at large numbers (65536 or higher) is CalculateListOfPrimes(...) at 67% of the total 15 second run time.
Switching the usage from a std::vector to a std::list (since I'm only adding to the END of the the list, it seemed like a good idea), only saved 5%.
Looking at it, the inner while loop is going through EVERY possible number from the currently known non-prime number to the next unknown number, is there an algorithm to tell what the next number to check should be or whether or not the next number and potentially every number after it is guaranteed NOT to be in the list of primes?
