[Math] How to find large prime factors without using computer

prime numbersproject euler

What is the largest prime factor of the number 600851475143 ?
This is the third problem of Project Euler.

How to approach this mathematically (without computer programming) ?

Best Answer

Well the point of Project Euler is to program. This is a problem that you could solve by hand but it would take you quite a while.

Factorisation is not a simple thing to do by hand for numbers this big (unless you have some special insight into divisibility by certain special primes).

Just use the bog standard test, square root and check divisibility of primes upto this. Once you find one, divide out and start again. In the end you will have a number that you cannot do this process to. This will be the largest prime factor.

Related Solutions

[Math] How to find the factors of numbers around 1e7

You can identify the prime factors of a number $n$ by testing the numbers $2,3,4,\ldots$ to see whether they divide $n$ and exit the loop when you either find a divisor $p$ or reach $\sqrt{n}$ (since if $n=ab$ then either $a$ or $b$ is at most $\sqrt{n}$, so if you reach $\sqrt{n}$ then $n$ is prime). If you find a divisor $p$, repeat this process with $n/p$. In this manner you get all the prime factors of $n$ (don't forget to include the $\sqrt{x}$ you get on your last iteration).

Once you have the prime factors, finding the divisors is easy. Suppose $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$. Then the divisors of $n$ are $p_1^{x_1}p_2^{x_2}\cdots p_k^{x_k}$ where $0\leq x_i\leq e_i$ for all $i\leq k$, thus the number of factors of $n$ is $(e_1+1)(e_2+1)\cdots(e_k+1)$ (as we have $e_i+1$ choices for each $x_i$, and two different choices give us two different divisors since prime factorizations are unique).

Prime Numbers – How to Find the Largest Prime Factor

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!

Best Answer

Related Solutions

[Math] How to find the factors of numbers around 1e7

Prime Numbers – How to Find the Largest Prime Factor

Related Question