notes.html
<article>
<h3>Problem Analysis</h3>
<p>
The task is to compute the 10,001st <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime number</a> - an integer greater than 1 whose only positive divisors are 1 and itself. Naively, I could test each candidate integer for primality by trial division, but that scales poorly. The efficient route is to generate primes in bulk with a sieve. The most familiar is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a>, but here I use its odd-only cousin, the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sieve of Sundaram</a>, which enumerates the odd primes directly by marking, for every pair <code>i, j</code>, the index <code>i + j + 2ij</code>. The surviving indices <code>k</code> then decode to the odd primes <code>2k+1</code>. Its marking cost is <code>O(M log M)</code> over a range of size <code>M</code> - far better than per-candidate trial division.
</p>
<p>
A sieve needs to know how large <code>M</code> must be to contain the n-th prime. This is where the <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number_theorem" rel="noopener noreferrer" target="_blank">prime number theorem</a> helps: it states that the n-th prime <code>p(n)</code> is asymptotically <code>n * ln(n)</code>, where <code>ln</code> is the natural logarithm. For <code>n = 10001</code>, that estimate is about 92,000, and the true answer is 104,743 - so the raw <code>n * ln(n)</code> heuristic is a little tight, but in this solution it works because the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sieve of Sundaram</a> indexes only odd numbers (each array index <code>k</code> stands for the much larger odd number <code>2k+1</code>), so the effective covered range is roughly doubled. The key observation that makes this fast is that we never need to consider even numbers beyond 2: every other even number is composite, so we sieve only odd numbers and halve both memory and work.
</p>
<h3>Solution Approach</h3>
<h4>Sieve of Sundaram (Solution 0 - Python and C)</h4>
<p>
Both the Python and C files implement the same <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sieve of Sundaram</a>, so I describe them together and note language differences as they arise.
</p>
<p>
<strong>Step 1 - Special-case the only even prime.</strong> 2 is the sole even prime. If <code>n == 1</code> I return 2 immediately; from then on I work only with odd numbers.
</p>
<p>
<strong>Step 2 - Size the sieve.</strong> I set <code>max_expected_value = int(n * log(n))</code>, the <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number_theorem" rel="noopener noreferrer" target="_blank">prime number theorem</a> estimate, and allocate an array of that length. Because each index <code>k</code> represents the odd number <code>2k+1</code>, the actual numeric range covered is about <code>2 * max_expected_value</code>, which comfortably contains the 10,001st prime.
</p>
<p>
<strong>Step 3 - Sieve over odd numbers.</strong> I map odd number <code>2k+1</code> to index <code>k</code>, initialising <code>numbers[k] = k</code> so a non-zero value means "still a candidate." The crucial algebra behind the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sieve of Sundaram</a>: multiplying two odd numbers gives <code>(2i+1)(2j+1) = 2(i + j + 2ij) + 1</code>, so their product corresponds to index <code>i + j + 2*i*j</code>. For each surviving index <code>i</code>, I set <code>numbers[i + j + 2*i*j] = 0</code> for <code>j</code> running from <code>i</code> upward, marking those composites. Starting <code>j</code> at <code>i</code> rather than 1 avoids re-marking products whose smaller factor was already processed.
</p>
<p>
<strong>Step 4 - Extract the answer.</strong> The surviving (non-zero) entries are the odd primes in order. I take the <code>(n-2)</code>-th surviving entry: the offset of -2 accounts for index 0 decoding to the non-prime 1, and for 2 already being counted as the 1st prime. I decode it back with <code>2*k + 1</code>.
</p>
<p>
<strong>Language differences.</strong> In Python the sieve is a list, and the inner loop relies on <code>try/except IndexError</code> to detect when the computed index runs past the end of the list, breaking out. In C, out-of-bounds writes are undefined behaviour, so I instead compute the index as a <code>long long</code> and explicitly compare <code>idx > max_expected_value</code> before writing; the C version also skips already-marked entries and frees the heap array at the end. Neither <code>solve()</code> parses arguments or times itself - that is the runner's job (see below).
</p>
</article>