Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 4 down vote accepted

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!

share|improve this answer

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

share|improve this answer

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

share|improve this answer
    
Someone posted this link on the forum of the project Euler. –  Vladimir Putin Aug 26 '12 at 20:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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