// primes.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <cmath>
#include <string>
#include <vector>

#include <chrono>

using namespace std;
using namespace std::chrono;

//unsigned long long origI = 3;
//unsigned long long n = 100000000;
unsigned int origI = 3;
unsigned int n = 100000;
vector<unsigned int> vprimes {2};

milliseconds ms1 = duration_cast<milliseconds>(
	system_clock::now().time_since_epoch()
);

int main()
{
	/*
	unsigned int count = 0;
	bool isprime;
	for (auto i=origI; i <= n; ++i) {
		//if ((int)pow(2, (i - 1)) % i != 1) continue;
		isprime = true;
		if (i % 2 == 0) isprime = false;
		for (int o = 3; o <= sqrt(i); o+=2) {
			if (i % o == 0) isprime = false;
		}
		if (isprime) {
			//cout << i << endl;
			++count;
		}
	}
	*/

	unsigned int count = 0;
	bool isprime;

	for (auto i = 3; i <= sqrt(n); ++i) {
		//if ((int)pow(2, (i - 1)) % i != 1) continue;
		isprime = true;
		if (i % 2 == 0) { isprime = false; continue; };


		for (auto p : vprimes) {
			if (p <= sqrt(i)) {
				if (i % p == 0) isprime = false;
			}
			else {
				break;
			}
		}
		if (isprime) {
			//cout << i << " added to fix" << endl;
			vprimes.push_back(i);
		}
	}

	for (auto i = origI; i <= n; ++i) {
		//if ((int)pow(2, (i - 1)) % i != 1) continue;
		isprime = true;
		if (i % 2 == 0) { isprime = false;continue; };


		for (auto p : vprimes) {
			if (p <= sqrt(i)) {
				if (i % p == 0) {
					isprime = false;
					break;
				}
			}
			else {
				break;
			}
		}
		if (isprime) {
			//cout << i << endl;
			++count;
			vprimes.push_back(i);
		}
	}
	
	
	

	milliseconds ms2 = duration_cast<milliseconds>(
		system_clock::now().time_since_epoch()
	);

	//cout << endl << endl << "There are " << count << " prime numbers between " << origI << " and " << n << endl << "The whole operation took about " << (long)ms2.count() - (long)ms1.count() << "ms to complete";
	cout << endl << endl << "There are " << count << " prime numbers between " << origI << " and " << n << endl << "The whole operation took about " << (long)ms2.count() - (long)ms1.count() << "ms to complete";
	
	
	/*

	vector:
		3 - 1'000'000 : 12784ms
		3 - 2'000'000 : 25227ms
		3 - 5'000'000 : 58557ms
	
	just loops:
		3 - 1'000'000 : 15135ms
		3 - 2'000'000 : 32723ms
		3 - 5'000'000 : 84439ms

	*/
}