notes.html
<article>
<h3>Problem Analysis</h3>
<p>
The goal is to find the largest <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a> divisor of a target integer. The natural tool is <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a>: I walk through candidate divisors in increasing order and remove each one that divides the number exactly. Two facts from elementary number theory turn this brute-force idea into an efficient one, and understanding why each holds is what lets me trust the result without any extra checks.
</p>
<p>
First, divisors come in pairs. If <code>d</code> divides <code>n</code> then so does <code>n/d</code>, and at least one member of each such pair is no larger than the square root of <code>n</code>. So if I scan candidates only up to the <a class="reference-source" href="https://en.wikipedia.org/wiki/Integer_square_root" rel="noopener noreferrer" target="_blank">integer square root</a> of the number and find no divisor, whatever remains cannot be composite — it must be <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a> itself. The search ceiling is therefore the square root of the value, not the value, which is the difference between an <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(sqrt(n))</a> method and a hopeless <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(n)</a> one.
</p>
<p>
Second, whenever I find a factor I divide it out <em>completely</em>, leaving a remainder that is <a class="reference-source" href="https://en.wikipedia.org/wiki/Coprime_integers" rel="noopener noreferrer" target="_blank">coprime</a> to it. This shrinks the remainder and, with it, the square-root ceiling — which I then recompute against the smaller remainder. For an input that is a few small <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">primes</a> times one large one, that ceiling collapses almost immediately once the small factors are stripped away. The worst case remains <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(sqrt(n))</a> — a genuinely <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a> input forces the loop all the way to its root — but typical inputs finish far sooner. There is a deeper payoff: because every smaller <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a> factor of a candidate is removed before the candidate is ever reached, any candidate that still divides the remainder must itself be <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a>. No explicit <a class="reference-source" href="https://en.wikipedia.org/wiki/Primality_test" rel="noopener noreferrer" target="_blank">primality test</a> is ever required.
</p>
<h3>Solution Approach</h3>
<h4>Trial Division with Aggressive Reduction (Python and C)</h4>
<p>
Both files share solution index 0 and implement the identical algorithm, so I describe them together and note the language differences at the end. The shape of the method is <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a> with complete reduction after every hit.
</p>
<p>
<strong>Special-case the factor 2.</strong> I test 2 once, before the loop. If it divides the number I call <code>reduce</code> to strip out every copy of 2 and set <code>largest_factor = 2</code>; otherwise I set <code>largest_factor = 1</code> as a harmless starting value. With the only even <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a> already handled, the main loop can step over odd candidates alone, halving its work.
</p>
<p>
<strong>The <code>reduce</code> helper.</strong> Given a number and a divisor known to divide it, <code>reduce</code> divides once and then keeps dividing while the divisor still goes in evenly, returning a value <a class="reference-source" href="https://en.wikipedia.org/wiki/Coprime_integers" rel="noopener noreferrer" target="_blank">coprime</a> to that divisor. This is the engine behind the no-<a class="reference-source" href="https://en.wikipedia.org/wiki/Primality_test" rel="noopener noreferrer" target="_blank">primality-test</a> guarantee: by fully eliminating each <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a> in order, I ensure a later composite candidate (say 9) cannot spuriously divide the remainder, because its <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a> constituent (3) was already removed.
</p>
<p>
<strong>Main loop over odd candidates.</strong> Starting at <code>current_factor = 3</code> and stepping by 2, I loop while the remainder exceeds 1 and the candidate is at most <code>search_limit</code> — the <a class="reference-source" href="https://en.wikipedia.org/wiki/Integer_square_root" rel="noopener noreferrer" target="_blank">integer square root</a> of the current remainder. Each time a divisor is found, I <code>reduce</code> the remainder, record the divisor in <code>largest_factor</code>, and recompute <code>search_limit</code> from the now-smaller remainder. That recomputation is the dynamic ceiling that makes the method fast in practice.
</p>
<p>
<strong>Final answer.</strong> When the loop ends, a remainder still greater than 1 has survived every <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a> up to its own square root and is therefore the largest <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a> factor, so I return it. Otherwise the last divisor removed during the loop is the answer.
</p>
<p>
The language differences are small. The C version uses <code>long long</code> to hold 64-bit values that would overflow a 32-bit <code>int</code>, computes the <a class="reference-source" href="https://en.wikipedia.org/wiki/Integer_square_root" rel="noopener noreferrer" target="_blank">integer square root</a> with <code>sqrt()</code> from <code><math.h></code> cast back to <code>long long</code>, and reads its input with <code>atoll</code>. The Python version uses the <code>**0.5</code> idiom and <code>int()</code> to truncate. Both truncate toward zero, which is correct here because the loop comparison is <code><=</code>, so flooring the limit never skips the boundary candidate.
</p>
</article>