Largest prime factor of a number

Question

In Project Euler problem 3, where we have to find the largest prime factor of a number, one of the solution i came across is

long long int find(long long int n){

    long k = 2;
    while (k * k <= n)
    {
        if (n % k == 0)
        {
            n /= k;
        }
        else
        {
            ++k;
        }
    }

    return n;
    }

The solution is perfect but i fail to understand the while condition here( while k*k<=n). Isnt the condition should be isPrime(n)? How does checking k*k<=n gives the right answer here?

Answer 1

The algorithm divides out all factors of $k=2$ from $n$, then all factors of $k=3$ from $n$, then $k=4$ (but there won't be any of those,) etc.

When $n>k>\sqrt{n}$, if $k\mid n$ then there was a smaller factor $\frac{n}{k}<k$ which was not factored out, which is not possible. So when $k>\sqrt{n}$, the only factor left will be $n$, and thus $n$ will be prime.

Here's a recursive/functional version of this same algorithm:

long long int find(long long int n) {
     return find_given_no_smaller_factors(n,2);
}

/*
 * Given that we know n has no prime factors smaller than k, find
 * largest prime factor of n
 */
long long int find_given_no_smaller_factors(long long int n,long long int k) {

    if (k*k>n) { return k; }

    if (n%k==0) { 
        return find_given_no_smaller_factors(n/k,k); 
    } else {
        return find_given_no_smaller_factors(n,k+1);
    }

}

Basically, when we check whether $k^2>n$, we already know that $n$ does not have any factors smaller than $k$. So $n$ must be prime.