/* (c) WhiZTiM ionogu (<_aT_>)acm(<dot>)org
   Thanks to Kenneth Nnani Ifeanyi
*/

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

using uint = unsigned int;

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";
}


std::vector<uint> sieve(uint limit=1'000'000)
{
    std::vector <uint> rtn;
    bool flag[1000000];
    flag[0] = true;
    flag[1] = true;
    for(uint i = 2; i < 1000000; i++)
    {
        if(not flag[i])
	{
	    // do all multiples
	    for(int j = 2*i; j <= 1000000; j+=i)
		flag[j] = true;
	}
    }

    for(uint i = 0; i <= 1000000; i++)
        if(not flag[i])
	    rtn.push_back(i);
    return rtn;
}

void run()
{
   std::ios_base::sync_with_stdio(0);
   auto a = sieve();
   long long int n = 600851475143 ;
    ///assumied all factors are less than 1000000
    std::vector <uint> result;
    while(n != 1)
    {
        for(uint i = 0; i < a.size(); i++)
        {
            if(n%a[i] == 0){result.push_back(a[i]); n = n/a[i]; break;}
        }
    }
    auto maxx = std::max_element(result.begin(), result.end());
    std::cout << "maximum factor is: " << *maxx << std::endl;
}

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