eratosthenes.cpp

Go to the documentation of this file.

 
#include <cassert>   
#include <chrono>    
#include <iostream>  
#include <string>    
#include <vector>    
 
namespace math {
void sieve(std::vector<bool> *vec) {
    (*vec)[0] = false;
    (*vec)[1] = false;
 
    // The sieve sets values to false as they are found not prime
    for (uint64_t n = 2; n < vec->size(); n++) {
        for (uint64_t multiple = n << 1; multiple < vec->size();
             multiple += n) {
            (*vec)[multiple] = false;
        }
    }
}
 
void print_primes(std::vector<bool> const &primes) {
    for (uint64_t i = 0; i < primes.size(); i++) {
        if (primes[i]) {
            std::cout << i << std::endl;
        }
    }
}
}  // namespace math
 
static void test() {
    auto primes = std::vector<bool>(10, true);
    math::sieve(&primes);
    assert(primes[0] == false);
    assert(primes[1] == false);
    assert(primes[2] == true);
    assert(primes[3] == true);
    assert(primes[4] == false);
    assert(primes[5] == true);
    assert(primes[6] == false);
    assert(primes[7] == true);
    assert(primes[8] == false);
    assert(primes[9] == false);
 
    std::cout << "All tests have successfully passed!\n";
}
 
int main(int argc, char *argv[]) {
    test();  // run self-test implementations
 
    // The largest prime we will check for
    auto max = 10000;
 
    // Store a boolean for every number which states if that index is prime or
    // not
    auto primes = std::vector<bool>(max, true);
 
    // Store the algorithm start time
    auto start = std::chrono::high_resolution_clock::now();
 
    // Run the sieve
    math::sieve(&primes);
 
    // Time difference calculation
    auto time = std::chrono::duration_cast<
                    std::chrono::duration<double, std::ratio<1>>>(
                    std::chrono::high_resolution_clock::now() - start)
                    .count();
 
    // Print the primes if we see that "print" was passed as an arg
    if (argc > 1 && argv[1] == std::string("print")) {
        math::print_primes(primes);
    }
 
    // Print the time taken we found earlier
    std::cout << "Time taken: " << time << " seconds" << std::endl;
 
    return 0;
}