find_primes.cpp

#include <chrono>
#include <iostream>
#include <vector>

template <typename T> std::vector<T> primes(T n) {
    bool *is_prime = new bool[n + 1];
    for (T i = 2; i <= n; i++) {
        is_prime[i] = true;
    }

    for (T i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (T j = i*i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    std::vector<T> primes;
    for (T i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
    delete[] is_prime;
    return primes;
}

int main(int argc, char *args[]) {
    // for (int p : primes(30)) {
    //     std::cout << p << " ";
    // }
    // std::cout << std::endl;
    auto start = std::chrono::high_resolution_clock::now();
    std::vector<unsigned long int> pr = primes<unsigned long int>(10000000);
    auto finish = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = finish - start;
    std::cout << "Elapsed time: " << elapsed.count() * 1000 << " ms\n";
    std::cout << "number of primes found: " << pr.size() << std::endl;
}

// g++ -O3 primes1.cpp && ./a.out
// Elapsed time: 44.8164 ms
// number of primes found: 664579