#include <iostream>
#include <set>
#include <cstdint>
#include <chrono>

//ver 0.3α

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

	//えーっと、2だけはどうやっても導き方がわからんのでハードコーディングで死守している。
	static std::set < std::uint64_t> Prime;//i need fast search structure
	static bool IsInit = false;

	bool Initialize(){
			Prime.insert(2);
			IsInit = true;

			return true;
	}

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

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

	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*o>i) break;//ttp://toro.2ch.net/test/read.cgi/tech/1390525149/393 method
				if (i%o == 0){
					F = false;
					break;
				}
			}
			if (F == true){
				Prime.insert(i);
				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 << ',';
		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 Number, std::uint64_t Count,  bool IsShow = false){

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

	SieveOfEratosthenes::IsPrime(Number);	
	SieveOfEratosthenes::FindToCount(SieveOfEratosthenes::GetCount()+Count);


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

	auto Eli = std::chrono::duration_cast<std::chrono::milliseconds>(E - S);
	if (IsShow == false) return true;
	std::cout << "経過時間は" << Eli.count() << "ミリ秒だ！" << std::endl;
	std::cout << SieveOfEratosthenes::GetCount() << "個発見して、最後の素数は" << SieveOfEratosthenes::GetLastFound() << "でした。" << std::endl;

	SieveOfEratosthenes::Show();


	return true;
}


int main(){

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

	MakeHoge(200000,100000 , true);

	return 0;
}