// G. Hagopian -- PPP4 Exercise 13

/*
13. Create a program to find all the prime numbers between 1 and 100. 
There is a classic method for doing this, called the "Sieve of Eratosthenes."
If you don’t know that method, get on the web and look it up. 
Write your program using this method.
*/

#include <iostream>
#include <vector>
#include <climits>
#include <ctime>
#include <ratio>
#include <chrono>
using namespace std;
using namespace std::chrono;
const unsigned max = 1000000;

bool isPrime2(int x, vector<int> primes) {
	for (int i = 0; primes[i] <= sqrt(x); ++i)
		if (x % primes[i] == 0) return false;
	return true;
}

//thanks to https://www.techiedelight.com/measure-elapsed-time-program-chrono-library/
// for the chrono code
int main() {
	auto start = std::chrono::high_resolution_clock::now();
	vector<bool> isPrime(max, true);
	vector<int> primes{ 2 };
	isPrime[0] = isPrime[1] = false;
	for (unsigned i = 2; 2 * i < max; ++i) isPrime[2 * i] = false;
	unsigned p = 3;
	while (p < sqrt(max)) {
		for (unsigned i = p; i * p < max; ++i) isPrime[i * p] = false;
		while (!isPrime[++p]);  //skip on to next prime
	}
	auto end = std::chrono::high_resolution_clock::now();
	auto time_span = std::chrono::duration_cast<std::chrono::duration<double>>(end - start);
	cout << "Computing primes less than " << max << " took "
		<< time_span.count() << endl;//std::chrono::duration_cast<chrono::nanoseconds>(end - start);
	cin.get();
	start = std::chrono::high_resolution_clock::now();
	for (int i = 3; i < max; ++i) {
		if (isPrime2(i, primes)) primes.push_back(i);
	}
	end = std::chrono::high_resolution_clock::now();
	time_span = std::chrono::duration_cast<std::chrono::duration<double>>(end - start);
	cout << "Computing primes less than " << max << " with the old method took "
		<< time_span.count() << endl;
	cin.get();
	for (int i = 0; i < max; ++i) 
		if(isPrime[i]) cout << i << " ";
}