//! (c) WhiZTiM __ionogu(<_at_)>acm.org

#include <cmath>
#include <vector>
#include <chrono>
#include <iostream>
#include <algorithm>

using uint64_t = std::uint64_t;
template<typename Func, typename... Args>
void timer(Func func, Args&&... args){
	auto start = std::chrono::high_resolution_clock::now();
	func(std::forward<Args&&>(args)...);
	auto stop = std::chrono::high_resolution_clock::now();
	std::cout.precision(8);
	std::cout << 
		"Took: " << std::chrono::duration<double, std::ratio<1,1>>(stop - start).count()
		<< " seconds\n";
}

class SimplePrimeGenerator {
public:		//intentional...
	std::vector<uint64_t> primes = {2, 3};
	std::size_t counter = 1;
public:
	uint64_t compute(std::size_t index){
		if(index < primes.size())
			return primes[index];
		primes.reserve(index);
		for(; counter < index; counter++){
			uint64_t prime1 = (6*counter - 1);
			uint64_t prime2 = (6*counter + 1);
			if(not sub_prime_factor_exists_for(prime1))
				primes.emplace_back(prime1);	//then it is a prime
			if(not sub_prime_factor_exists_for(prime2))
				primes.emplace_back(prime2);	//ditto ^^
		}
		return primes[index];
	}
	
	bool prime_factor_exists_for(uint64_t number) {
		if (not std::binary_search(primes.begin(), primes.end(), number))
			compute(std::sqrt(number) + 1);
		return std::binary_search(primes.begin(), primes.end(), number);
	}
	
	inline bool sub_prime_factor_exists_for(uint64_t num) const {
		for(auto x : primes)
			if(num % x == 0 and num != x)
				return true;
		return false;
	}
};

std::vector<std::size_t> simple_factors(uint64_t number){
	std::vector<std::size_t> rtn;
	std::size_t bound = std::sqrt(number);
	for(std::size_t i=1; i <= bound; i++)
		if(number % i == 0){
			rtn.emplace_back(i);
			rtn.emplace_back(number / i);
		}
	std::sort(rtn.begin(), rtn.end());
	return rtn;
}

int mainc(){
	auto pf = simple_factors(600851475143ull);
	//auto pf = simple_factors(13195);
	SimplePrimeGenerator spg;
	for(auto k = pf.rbegin(); k != pf.rend(); ++k )
		if(spg.prime_factor_exists_for(*k)){
			std::cout << "Largest prime factor of 600851475143 is " << *k << "\n";
			break;
		}
	return 0;
}

int main(){
	timer(mainc);
	return 0;
}