Found 3401 small primes in 0.5ms
Sieve: Found 4838319 primes in 0.296255s
Naive: Found 4838319 primes in 25.4289s#include <iostream>
#include <vector>
#include <chrono>
#include <cmath>
const int BE = 900000000;
const int N = 1000000000;
std::vector<int> small_primes;
bool DivisibleBySmallPrimes(int x) {
for (int i = 0; i < (int)small_primes.size() && small_primes[i]*small_primes[i] <= x; ++i) {
if (x % small_primes[i] == 0) return true;
}
return false;
}
void ComputeSmallPrimes() {
auto start = std::chrono::steady_clock::now();
int n = sqrt(N);
for (int i = 2; i <= n; ++i) {
if (!DivisibleBySmallPrimes(i)) {
small_primes.push_back(i);
}
}
auto end = std::chrono::steady_clock::now();
std::chrono::duration<double> elapsed_seconds = end-start;
std::cout << "Found " << small_primes.size() << " small primes in " << elapsed_seconds.count()*1000 << "ms\n";
}
void ComputeSieve() {
auto start = std::chrono::steady_clock::now();
std::vector<bool> sieve(N-BE+1);
std::vector<int> primes;
for (auto &x : small_primes) {
int i = (BE-1) - (BE-1) % x + x;
while (i <= N) {
sieve[i-BE] = true;
i += x;
}
}
for (int i = BE; i <= N; ++i) {
if(!sieve[i-BE]) {
primes.push_back(i);
}
}
auto end = std::chrono::steady_clock::now();
std::chrono::duration<double> elapsed_seconds = end-start;
std::cout << "Sieve: Found " << primes.size() << " primes in " << elapsed_seconds.count() << "s\n";
}
void ComputeNaive() {
auto start = std::chrono::steady_clock::now();
std::vector<int> primes;
for (int i = BE; i <= N; ++i) {
if (!DivisibleBySmallPrimes(i)) {
primes.push_back(i);
}
}
auto end = std::chrono::steady_clock::now();
std::chrono::duration<double> elapsed_seconds = end-start;
std::cout << "Naive: Found " << primes.size() << " primes in " << elapsed_seconds.count() << "s\n";
}
int main() {
ComputeSmallPrimes();
ComputeSieve();
ComputeNaive();
return 0;
}int is_ordered(int* array, int size) {
for(int i = 1; i < size; i++) {
if (array[i] < array[i-1]) return FALSE;
}
return TRUE;
}