Prime Numbers – How to Find the Largest Prime Factor

divisibilityfactoringprime numbersproject euler

I just "solved" the third Project Euler problem:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

With this on Mathematica:

Select[Divisors[600851475143], PrimeQ]

It will first give me a list with all the divisors of 600851475143 and then It's going to select the prime ones, giving me:

{71, 839, 1471, 6857}

And thus giving me the answer of 6857. I feel that my solution won't give me better insights into this (since I used almost null mental activity for it) and I would like to know how can I extend this problem, what other ways are accessible on solving it?

I initially thought that I should applying the idea of divisibility, some guys on the PE solved it using the sieve of Eratosthenes, can you suggest other ways that could solve this problem?

Thanks in advance.

Best Answer

In general factoring problem is not easy, see:Theoretical Computer Science Q&A
There is a Pollard-Rho algorithm which you can find some information here: Wikipedia: Factoring integers
I solved that problem of Project Euler too! The output of MATLAB is:

   71

   839

        1471

        6857

Elapsed time is 0.002433 seconds.
>>

And the code in MATLAB:

clear;
clc;
tic;
p=600851475143 ;
m=3;
while(sqrt(m)<p)
    j=rem(p,m);
    if (j==0)
        p=p/m;
        disp(m);
        m=m+2;
    else
        m=m+2;
    end
end
toc;

By the way, there is factor command in MATLAB that directly outputs the factors of a number. But it has a 2^32 of input limitation size. I removed the limitation of the original code and it responded in 0.027501 seconds!

Related Question