#include <cstdint>
#include <iostream>
#include <cmath>
#include <vector>

bool prime( std::uintmax_t number, const std::vector<bool>& sieve )
{
    const std::size_t SZ = std::ceil( std::sqrt(number) ) + 1 ;
    for( std::size_t i = 2 ; i < SZ ; ++i )
        if( sieve[i] && !(number%i) ) return false ;
    return true ;
}

int main()
{
    std::uintmax_t N ;
    if( std::cout << "N? " && std::cin >> N )  // 600851475143 ;
    {
        const std::size_t SZ = std::ceil( std::sqrt(N) ) + 1 ;

        // generate a prime number sieve upto the square root of N
        std::vector<bool> sieve( SZ, true ) ;
        for( std::size_t i = 2 ; i < SZ ; ++i ) if( sieve[i] )
              for( auto j = i*i ; j < SZ ; j += i ) sieve[j] = false ;

        std::uintmax_t largest_prime_factor = 1 ;

        // start with 1 because N may be a prime
        for( std::size_t i = 1 ; i < SZ ; ++i ) if( sieve[i] && N%i == 0 )
        {
            if( prime( N/i, sieve ) )
            {
               largest_prime_factor = N/i ;
               break ; // N == x*i, x>sqrt(i), and x is a prime
            }
            else largest_prime_factor = i ;
        }

        std::cout << "largest prime factor of " << N << " is "
                   << largest_prime_factor << '\n' ;
    }
}