0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I didnt get anything though. $\endgroup$ – Diffy Sep 13 '14 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.