Original problem

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

What is the largest prime factor of the number $600851475143$?

Formal statement

For

$$N=600851475143,$$

find

$$max\{p\in \mathbb{P}\mid p\mid N\},$$

where $\mathbb{P}$ is the set of prime numbers.

Hints

Open one at a time

Remove each small factor completely before continuing.

When the loop ends, the remaining number may itself be prime.

Solution

Best opened after a real attempt

Approach

Start with the smallest possible divisor. Whenever the current divisor divides the remaining value, divide it out completely before moving on. Each successful division shrinks the unresolved part of the factorization.

It is enough to test divisors while $d^2\le n$. If a value greater than $1$ remains after that point, it cannot have a smaller undiscovered factor and is therefore prime. The largest divisor removed—or that final remainder—is the required factor.

Code & final result

Password-protected content

Enter the access password. Decryption happens only in this browser.

Access password

The original problem is reproduced from Project Euler Problem 3 under CC BY-NC-SA 4.0.