Return to Question

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?

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?

Currently the major bottleneck at large numbers (65536 or higher) is CalculateListOfPrimes(...) at 67% of the total 15 second run time.

EDIT:

Here is the final code as requested, for completeness I've included the entire code listing. After profiling some more, the only bottleneck that I have control of is the ParseElapsedTime(...) function (the other bottleneck is when DisplayResults(...) prints the list but that's expected.) All things considered, it running 22% of an 8 millisecond run is inconsequential.

#include <iostream>
#include <ctime>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <vector>

#define PAUSE { system("pause"); }

void DisplayHelp();
time_t StartTimer();
double EndTimer(const time_t startTime);
void ParseElapsedTime(const double elapsedTime);
int ParseCommandLineArguments(char** argv);
unsigned int CalculateSumOfPrimes(const unsigned int number);
std::vector<bool> CalculateListOfPrimes(const unsigned int number);
void DisplayResult(std::vector<bool>* container, const unsigned int sum);

int main(int argc, char** argv) {
    if(argc != 3) {
        DisplayHelp();
        PAUSE
        return 0;
    }

    int successful_parse = ParseCommandLineArguments(argv);
    if(successful_parse == 0) {
        PAUSE
        return 0;
    }

    time_t startTime = 0;
    std::cout << "Initializing..." << std::endl;
    startTime = StartTimer();
    std::cout << "Calculating..." << std::endl;
    bool displayAsList = successful_parse == 1;
    if(displayAsList) {
        std::vector<bool> primes;
        primes = CalculateListOfPrimes(std::atoi(argv[2]));
        std::cout << "Generating Result..." << std::endl;
        DisplayResult(&primes, 0);
    } else {
        //Only remaining option is to display as a sum of numbers.
        unsigned int sum = CalculateSumOfPrimes(std::atoi(argv[2]));
        std::cout << "Generating Result..." << std::endl;
        DisplayResult(NULL, sum);
    }


    std::cout << "\nDone.." << std::endl;

    double elapsedTime = 0.0;
    elapsedTime = EndTimer(startTime);
    ParseElapsedTime(elapsedTime);
    PAUSE
    return 0;
}

void DisplayHelp() {
    std::cout << "Usage: Sieve.exe -s X";
    std::cout << "\nDisplays the sum of all primes below the max number X.";
    std::cout << "\nSieve.exe -l X";
    std::cout << "\nDisplays all prime numbers below the max number X." << std::endl;
}

time_t StartTimer() {
    time_t startTime;
    time(&startTime);
    return startTime;
}

double EndTimer(const time_t startTime) {
    if(startTime == 0) return 0.0;
    time_t endTime;
    time(&endTime);
    return difftime(endTime, startTime);
}

void ParseElapsedTime(const double elapsedTime) {
    double remaining_seconds = elapsedTime;
    
    const unsigned int SECONDS_PER_DAY = 86400;
    unsigned long days = static_cast<unsigned long>(remaining_seconds / SECONDS_PER_DAY);
    remaining_seconds = std::fmod(remaining_seconds, SECONDS_PER_DAY);
    
    const unsigned int SECONDS_PER_HOUR = 3600;
    unsigned long hours = static_cast<unsigned long>(remaining_seconds / SECONDS_PER_HOUR);
    remaining_seconds = std::fmod(remaining_seconds, SECONDS_PER_HOUR);
    
    const unsigned int SECONDS_PER_MINUTE = 60;
    unsigned long minutes = static_cast<unsigned long>(remaining_seconds / SECONDS_PER_MINUTE);
    remaining_seconds = std::fmod(remaining_seconds, SECONDS_PER_MINUTE);
    
    unsigned long seconds = static_cast<unsigned long>(remaining_seconds);
    
    std::cout << "Elapsed Time: " << days << " D ";
    std::cout                     << hours << " H ";
    std::cout                     << minutes << " M ";
    std::cout                     << seconds << " S" << std::endl;
}

int ParseCommandLineArguments(char** argv) {

    bool isListArg = (std::strcmp("-l", argv[1]) == 0 ? true : false);
    bool isSumArg = (std::strcmp("-s", argv[1]) == 0 ? true : false);
    bool isCorrectArg = isListArg || isSumArg;
    if(isCorrectArg) {
        unsigned int max_bound = std::atoi(argv[2]);
        if(max_bound < 0 || max_bound >= UINT_MAX) {
            std::cout << "Max number outside valid range: 0 - " << UINT_MAX << std::endl;
            return 0;
        }
        if(isListArg) {
            return 1;
        } else if(isSumArg) {
            return -1;
        }
    } else {
        std::cout << "Incorrect argument. Use -l or -s or -help only." << std::endl;
        return 0;
    }
    std::cout << "Unknown argument error." << std::endl;
    return 0;
}

unsigned int CalculateSumOfPrimes(const unsigned int number) {
    if(number <= 1) return 0;
    if(number == 2) return 2;
    std::vector<bool> listOfPrimes;
    listOfPrimes = CalculateListOfPrimes(number);
    unsigned int sum = 0;
    for(unsigned int i = 0; i < listOfPrimes.size(); ++i) {
        if(listOfPrimes[i] == true) sum += i;
    }
    return sum;
}

std::vector<bool> CalculateListOfPrimes(const unsigned int number) {
    std::vector<bool> sieve(number + 1, true);
    sieve[2] = false;
    unsigned int current_prime_check = 2;
    while(current_prime_check < number) {
        for(unsigned int i = 2 * current_prime_check; i < number; i += current_prime_check) {
            sieve[i] = false;
        }
        ++current_prime_check;
        while(sieve[current_prime_check] == false) {
            ++current_prime_check;
        }
    }
    return sieve;
}

void DisplayResult(std::vector<bool>* container, const unsigned int sum) {
    if(container == NULL && sum == 0) {
        return;
    }

    if(sum != 0) {
        std::cout << "Sum of Primes: " << sum << std::endl;
        return;
    } else if(container != NULL) {
        std::cout << "List of Primes:" << std::endl;
        for(unsigned int i = 1; i < container->size(); ++i) {
            if(container->at(i) == true) std::cout << std::setw(15) << std::right << i << std::endl;
        }
    }
}

Currently the major bottleneck at large numbers (65536 or higher) is CalculateListOfPrimes(...) at 67% of the total 15 second run time.

Currently the major bottleneck at large numbers (65536 or higher) is CalculateListOfPrimes(...) at 67% of the total 15 second run time.

Currently the major bottleneck at large numbers (65536 or higher) is CalculateListOfPrimes(...) at 67% of the total 15 second run time.

EDIT:

Here is the final code as requested, for completeness I've included the entire code listing. After profiling some more, the only bottleneck that I have control of is the ParseElapsedTime(...) function (the other bottleneck is when DisplayResults(...) prints the list but that's expected.) All things considered, it running 22% of an 8 millisecond run is inconsequential.

#include <iostream>
#include <ctime>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <vector>

#define PAUSE { system("pause"); }

void DisplayHelp();
time_t StartTimer();
double EndTimer(const time_t startTime);
void ParseElapsedTime(const double elapsedTime);
int ParseCommandLineArguments(char** argv);
unsigned int CalculateSumOfPrimes(const unsigned int number);
std::vector<bool> CalculateListOfPrimes(const unsigned int number);
void DisplayResult(std::vector<bool>* container, const unsigned int sum);

int main(int argc, char** argv) {
    if(argc != 3) {
        DisplayHelp();
        PAUSE
        return 0;
    }

    int successful_parse = ParseCommandLineArguments(argv);
    if(successful_parse == 0) {
        PAUSE
        return 0;
    }

    time_t startTime = 0;
    std::cout << "Initializing..." << std::endl;
    startTime = StartTimer();
    std::cout << "Calculating..." << std::endl;
    bool displayAsList = successful_parse == 1;
    if(displayAsList) {
        std::vector<bool> primes;
        primes = CalculateListOfPrimes(std::atoi(argv[2]));
        std::cout << "Generating Result..." << std::endl;
        DisplayResult(&primes, 0);
    } else {
        //Only remaining option is to display as a sum of numbers.
        unsigned int sum = CalculateSumOfPrimes(std::atoi(argv[2]));
        std::cout << "Generating Result..." << std::endl;
        DisplayResult(NULL, sum);
    }


    std::cout << "\nDone.." << std::endl;

    double elapsedTime = 0.0;
    elapsedTime = EndTimer(startTime);
    ParseElapsedTime(elapsedTime);
    PAUSE
    return 0;
}

void DisplayHelp() {
    std::cout << "Usage: Sieve.exe -s X";
    std::cout << "\nDisplays the sum of all primes below the max number X.";
    std::cout << "\nSieve.exe -l X";
    std::cout << "\nDisplays all prime numbers below the max number X." << std::endl;
}

time_t StartTimer() {
    time_t startTime;
    time(&startTime);
    return startTime;
}

double EndTimer(const time_t startTime) {
    if(startTime == 0) return 0.0;
    time_t endTime;
    time(&endTime);
    return difftime(endTime, startTime);
}

void ParseElapsedTime(const double elapsedTime) {
    double remaining_seconds = elapsedTime;
    
    const unsigned int SECONDS_PER_DAY = 86400;
    unsigned long days = static_cast<unsigned long>(remaining_seconds / SECONDS_PER_DAY);
    remaining_seconds = std::fmod(remaining_seconds, SECONDS_PER_DAY);
    
    const unsigned int SECONDS_PER_HOUR = 3600;
    unsigned long hours = static_cast<unsigned long>(remaining_seconds / SECONDS_PER_HOUR);
    remaining_seconds = std::fmod(remaining_seconds, SECONDS_PER_HOUR);
    
    const unsigned int SECONDS_PER_MINUTE = 60;
    unsigned long minutes = static_cast<unsigned long>(remaining_seconds / SECONDS_PER_MINUTE);
    remaining_seconds = std::fmod(remaining_seconds, SECONDS_PER_MINUTE);
    
    unsigned long seconds = static_cast<unsigned long>(remaining_seconds);
    
    std::cout << "Elapsed Time: " << days << " D ";
    std::cout                     << hours << " H ";
    std::cout                     << minutes << " M ";
    std::cout                     << seconds << " S" << std::endl;
}

int ParseCommandLineArguments(char** argv) {

    bool isListArg = (std::strcmp("-l", argv[1]) == 0 ? true : false);
    bool isSumArg = (std::strcmp("-s", argv[1]) == 0 ? true : false);
    bool isCorrectArg = isListArg || isSumArg;
    if(isCorrectArg) {
        unsigned int max_bound = std::atoi(argv[2]);
        if(max_bound < 0 || max_bound >= UINT_MAX) {
            std::cout << "Max number outside valid range: 0 - " << UINT_MAX << std::endl;
            return 0;
        }
        if(isListArg) {
            return 1;
        } else if(isSumArg) {
            return -1;
        }
    } else {
        std::cout << "Incorrect argument. Use -l or -s or -help only." << std::endl;
        return 0;
    }
    std::cout << "Unknown argument error." << std::endl;
    return 0;
}

unsigned int CalculateSumOfPrimes(const unsigned int number) {
    if(number <= 1) return 0;
    if(number == 2) return 2;
    std::vector<bool> listOfPrimes;
    listOfPrimes = CalculateListOfPrimes(number);
    unsigned int sum = 0;
    for(unsigned int i = 0; i < listOfPrimes.size(); ++i) {
        if(listOfPrimes[i] == true) sum += i;
    }
    return sum;
}

std::vector<bool> CalculateListOfPrimes(const unsigned int number) {
    std::vector<bool> sieve(number + 1, true);
    sieve[2] = false;
    unsigned int current_prime_check = 2;
    while(current_prime_check < number) {
        for(unsigned int i = 2 * current_prime_check; i < number; i += current_prime_check) {
            sieve[i] = false;
        }
        ++current_prime_check;
        while(sieve[current_prime_check] == false) {
            ++current_prime_check;
        }
    }
    return sieve;
}

void DisplayResult(std::vector<bool>* container, const unsigned int sum) {
    if(container == NULL && sum == 0) {
        return;
    }

    if(sum != 0) {
        std::cout << "Sum of Primes: " << sum << std::endl;
        return;
    } else if(container != NULL) {
        std::cout << "List of Primes:" << std::endl;
        for(unsigned int i = 1; i < container->size(); ++i) {
            if(container->at(i) == true) std::cout << std::setw(15) << std::right << i << std::endl;
        }
    }
}