# Find the largest prime factor

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?

-
This number is computationally quite small for integer factorisation so any method will do really... As for using almost no brain power, this is only the third problem so is taken to be relatively quite simple in comparison to the later ones. – fretty Aug 26 '12 at 13:10

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!

-

For numbers of such small magnitude I find it most convenient to use factor, a GNU/Linux command-line utility.

-
I liked both factor and the "small magnitude" comment. Thank you! – LIttle Ancient Forest Kami Jan 4 '15 at 20:36

Did you try: http://www.alpertron.com.ar/ECM.HTM

-
Someone posted this link on the forum of the project Euler. – Voyska Aug 26 '12 at 20:31

Here is an example using JavaScript

function largestPrimeFactor(val, divisor = 2) {
let square = (val) => Math.pow(val, 2);

while ((val % divisor) != 0 && square(divisor) <= val) {
divisor++;
}

return square(divisor) <= val
? largestPrimeFactor(val / divisor, divisor)
: val;
}

-