#include <iostream>
#include <map>
#include <cstdint>
#include <chrono>

namespace SieveOfEratosthenes{//追記型エラトステネスの篩

	//えーっと、Prime[2]=trueだけはどうやっても導き方がわからんのでハードコーディングで死守している。
	typedef std::uint8_t Dummy;//need low volume storage.
	static std::map < std::uint64_t, Dummy> Prime;//i need fast search structure
	static bool IsInit = false;
	static Dummy TValue = 1;

	bool Initialize(){
			Prime[2] = true;
			IsInit = true;

			return true;
	}

	std::uint64_t GetLastFound(){
		if (IsInit == false) Initialize();

		return (*(Prime.rbegin())).first;
	}

	std::size_t GetCount(){
		return Prime.size();
	}

	bool FindNextPrime(){
		if (IsInit == false) Initialize();

		std::uint64_t i = GetLastFound() + 1;
		bool F = true;

		while (true){
			F = true;
			for (auto& o : Prime){
				if (o.first > ((i / 2) + 2)) break;
				if (i%o.first == 0){
					F = false;
					break;
				}
			}
			if (F == true){
				Prime[i] = TValue;
				return true;
			}
			i++;
		}
	}
	bool Clear(){
		Prime.clear();
		IsInit = false;
		return true;
	}
	bool FindToCount(std::uint64_t N){
		while (Prime.size() < N){
			FindNextPrime();
		}

		return true;
	}

	bool IsPrime(std::uint64_t N){

		while (GetLastFound() < N){
			FindNextPrime();
		}
		auto it = Prime.find(N);

		return (it != Prime.end());
	}

	bool Show(){
		std::cout << "Result:" << std::endl;
		for (auto& o : Prime) std::cout << o.first << ',';
		std::cout << std::endl;

		return true;
	}

}

bool BenchMarkByNumber(std::size_t N,bool IsShow = false){

	SieveOfEratosthenes::Clear();

	auto S=std::chrono::system_clock::now();

	bool b3 = SieveOfEratosthenes::IsPrime(N);

	auto E = std::chrono::system_clock::now();

	auto Eli = std::chrono::duration_cast<std::chrono::milliseconds>(E - S);

	std::cout << "経過時間は" << Eli.count() << "ミリ秒だ！" << std::endl;

	if (IsShow == false) return true;

	SieveOfEratosthenes::Show();

	std::cout << "経過時間は" << Eli.count() << "ミリ秒だ！" << std::endl;

	std::cout << SieveOfEratosthenes::GetCount() << "個発見して、最後の素数は" << SieveOfEratosthenes::GetLastFound() << "でした。" << std::endl;
	
	return true;
}

bool BenchMarkByCount(std::size_t N, bool IsShow = false){

	SieveOfEratosthenes::Clear();

	auto S=std::chrono::system_clock::now();

	SieveOfEratosthenes::FindToCount(N);

	auto E = std::chrono::system_clock::now();

	auto Eli = std::chrono::duration_cast<std::chrono::milliseconds>(E - S);

	if (IsShow == false) return true;

	SieveOfEratosthenes::Show();

	std::cout << "経過時間は" << Eli.count() << "ミリ秒だ！" << std::endl;
	std::cout << SieveOfEratosthenes::GetCount() << "個発見して、最後の素数は" << SieveOfEratosthenes::GetLastFound() << "でした。" << std::endl;

	return true;

}

bool MakeHoge(std::uint64_t Count, std::uint64_t Number, bool IsShow = false){

	auto S=std::chrono::system_clock::now();
	
	SieveOfEratosthenes::FindToCount(Count);
	SieveOfEratosthenes::IsPrime(SieveOfEratosthenes::GetLastFound() + Number);

	auto E = std::chrono::system_clock::now();

	auto Eli = std::chrono::duration_cast<std::chrono::milliseconds>(E - S);
	if (IsShow == false) return true;
	SieveOfEratosthenes::Show();

	std::cout << "経過時間は" << Eli.count() << "ミリ秒だ！" << std::endl;
	std::cout << SieveOfEratosthenes::GetCount() << "個発見して、最後の素数は" << SieveOfEratosthenes::GetLastFound() << "でした。" << std::endl;
	return true;
}


int main(){

	//BenchMarkByNumber(10000,true);
	//BenchMarkByCount(1000, true);

	MakeHoge(5000, 50000, true);

	return 0;
}