Detailed mathematical approach

Problem Summary

The task is to determine the largest prime factor of \(600851475143\). The sample value \(13195\) is useful because it already shows the shape of the question:

$13195 = 5 \cdot 7 \cdot 13 \cdot 29,$

so its largest prime factor is \(29\). The implementation solves the same problem for the much larger target integer by repeatedly removing prime divisors from a shrinking remainder.

Mathematical Approach

The solution is a careful form of trial division. Its correctness does not come from blindly testing divisors; it comes from an invariant about what the remaining number can still contain after smaller factors have already been removed.

Prime Factorization and the Quantity We Need

By the fundamental theorem of arithmetic, every integer \(N \ge 2\) can be written uniquely as

$N = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}, \qquad 2 \le p_1 \lt p_2 \lt \cdots \lt p_r,$

with each \(a_i \ge 1\). The answer to the problem is simply \(p_r\), the largest prime appearing in that factorization.

The difficulty is that we do not know the factorization in advance. The algorithm reconstructs only the part it needs: it keeps removing confirmed prime factors until the remaining value is either \(1\) or itself prime.

The Shrinking Remainder Invariant

Suppose we have already finished processing every possible divisor below some odd candidate \(d\). Let the current remainder be \(n\). Then the invariant is:

$N = \left(\prod_{p \lt d} p^{e_p}\right) n,$

where the product contains exactly the prime powers that have already been removed, and \(n\) has no prime factor smaller than \(d\).

This immediately explains two key implementation decisions.

First, the factor \(2\) is handled separately at the beginning. After repeatedly dividing by \(2\), the remainder becomes odd, so the rest of the search only needs odd candidates.

Second, when an odd candidate \(d\) divides the current remainder, \(d\) must actually be prime. If it were composite, it would have a prime divisor \(q \lt d\). That same \(q\) would also divide the current remainder, contradicting the invariant that no smaller prime factors remain. So even though the loop steps through all odd integers, every successful odd divisor is automatically a prime factor.

The algorithm also divides that factor out completely. If \(d^k \mid n\), then after the inner loop finishes we have removed all copies of \(d\), which restores the same invariant for the next candidate.

Why the Loop Stops at the Square Root of the Current Remainder

The classical bound is: if a positive integer \(m\) is composite, then it has a prime factor at most \(\sqrt{m}\). Indeed, if \(m = ab\) with \(1 \lt a \le b\), then \(a^2 \le ab = m\), hence \(a \le \sqrt{m}\), and some prime dividing \(a\) also divides \(m\).

Apply that statement not to the original input, but to the current remainder. If the current remainder \(n\) were composite, then some prime factor would be at most \(\sqrt{n}\). Therefore, once the current candidate exceeds \(\sqrt{n}\), there are only two possibilities left:

• \(n = 1\), meaning every prime factor has already been removed.
• \(n \gt 1\), in which case \(n\) itself must be prime.

This is why the stopping condition tightens as the remainder shrinks. The search bound is not fixed at \(\sqrt{N}\); it gets smaller every time a factor is divided out. The C++ implementation expresses this test in an overflow-safe division form, while the Python and Java implementations use the equivalent square comparison.

Worked Example: \(13195\)

Start with \(n = 13195\). The number is odd, so there is no factor \(2\) to remove.

Testing odd candidates in increasing order, the first successful divisor is \(5\):

$13195 \div 5 = 2639.$

The remainder \(2639\) is not divisible by \(5\) again, so the search continues. The next successful divisor is \(7\):

$2639 \div 7 = 377.$

Then \(13\) divides:

$377 \div 13 = 29.$

Now the remainder is \(29\). At that point the next candidate would already exceed \(\sqrt{29}\), so the loop stops. Because a composite remainder would need a factor at most \(\sqrt{29}\), the remaining \(29\) must be prime. Hence the largest prime factor is \(29\).

Applying the Same Reasoning to \(600851475143\)

The target number behaves exactly the same way. Repeated trial division removes the prime factors in increasing order:

$600851475143 = 71 \cdot 839 \cdot 1471 \cdot 6857.$

After dividing out \(71\), then \(839\), then \(1471\), the remaining value is \(6857\). No smaller factor remains, and once the search bound passes \(\sqrt{6857}\), that remainder is forced to be prime. Therefore the final answer is \(6857\).

Kodun Çalışma Mantığı

The C++, Python, and Java implementations all follow the same mathematical plan: maintain a mutable remainder, keep track of the largest confirmed prime factor seen so far, and shrink the remainder whenever a factor is found.

Removing the Factor \(2\)

The first phase repeatedly divides by \(2\) while the input is even. This isolates the only even prime immediately. If at least one such division happens, then the best answer found so far is at least \(2\), and the remainder becomes odd.

Scanning Odd Candidates

After that, the implementation checks odd candidates \(3, 5, 7, \dots\) in ascending order. Whenever the current candidate divides the remainder, the implementation divides repeatedly until that factor disappears completely, and then updates the current best answer. This corresponds exactly to removing the full prime power \(p^a\) from the factorization before moving on.

Because the remainder keeps shrinking, the stopping condition is evaluated against the current remainder rather than against the original input. That is the reason the algorithm is usually much faster than a naive fixed-bound scan would suggest.

The Last Remainder

When the odd-candidate loop ends, the implementation performs one final check. If the remainder is still greater than \(1\), it must be prime by the square-root argument above, so it becomes the answer. Each implementation also verifies the sample case \(13195 \mapsto 29\) before printing the result for the main input.

Complexity Analysis

In the worst case, trial division checks odd numbers up to about \(\sqrt{N}\), so the running time is \(O(\sqrt{N})\). The algorithm uses only a constant amount of extra memory, so the space complexity is \(O(1)\).

That worst case is already modest for this specific input: \(\sqrt{600851475143}\) is about \(7.75 \times 10^5\), and only odd candidates are tested after the factor \(2\) is handled. In practice the dynamic bound shrinks whenever a factor is removed, so the real running time is smaller than the pessimistic bound suggests.

Footnotes and References

1. Project Euler Problem 3
2. Fundamental theorem of arithmetic
3. Prime factor
4. Trial division
5. Integer factorization overview