Largest prime factor of a number

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?

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.

• Thanks. I didnt get anything though. Commented Sep 13, 2014 at 18:17