notes.html
problem 35 · 68 lines
<article>
<h3>Problem Analysis</h3>
<p>
A <em>circular prime</em> is a prime number whose every cyclic rotation of decimal digits is
also prime. For 197 the rotations 197, 971, and 719 are all prime, so it qualifies. The task is
to count circular primes below one million. The naive approach - take every prime, generate its
rotations, and test each rotation for primality - is correct but asks the same primality
questions over and over. Two observations turn this into a quick search.
</p>
<p>
The first is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Divisibility_rule" rel="noopener noreferrer" target="_blank">divisibility</a>
argument that prunes almost the entire candidate set. If a multi-digit number contains any of
the digits 0, 2, 4, 5, 6, or 8, then some rotation places that digit in the units position. A
number ending in an even digit is divisible by 2; a number ending in 0 or 5 is divisible by 5.
Either way that rotation exceeds 5 and is composite, so the original cannot be a circular prime.
Therefore every multi-digit circular prime is built only from the digits 1, 3, 7, and 9 - a tiny
fraction of all integers. The single-digit primes 2, 3, 5, and 7 are trivially circular and are
handled as a special case. The second observation is that primality is queried many times - once
per rotation per surviving candidate - so I should precompute it. The standard tool is a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a>,
which marks all composites up to a limit <code>n</code> in O(n log log n) time and O(n) space,
after which a primality test is an O(1) array lookup. Sieve construction dominates the runtime;
the rotation phase adds only a small constant amount of work per surviving candidate (at most 7
rotations below 10^7).
</p>
<h3>Solution Approach</h3>
<h4>Hand-rolled Sieve (Eratosthenes in C, Sundaram in Python)</h4>
<p>
Both index-0 files build their own sieve, then apply the digit filter and rotation check. The C
version (<code>p0035_s0.c</code>) uses a classic
<a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a>
over a <code>calloc</code>-zeroed byte array where <code>sieve[i] = 1</code> means composite. It
iterates <code>i</code> from 2 up to <code>sqrt(max_num)</code>, and for each prime marks
multiples starting at <code>i*i</code> - everything smaller has already been marked by a smaller
factor, so this avoids redundant work. The Python version (<code>p0035_s0.py</code>) uses a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sieve of Sundaram</a>:
it marks integers of the form <code>i + j + 2*i*j</code> as composite, then each unmarked index
<code>k</code> maps to the odd prime <code>2k+1</code>, with 2 added explicitly. Sundaram works
only over odd numbers, halving the working array at the cost of a slightly less cache-friendly
access pattern. Both are correct ways to enumerate primes.
</p>
<p>
Having the primes, both iterate over them. Single-digit primes are counted immediately. For
larger primes, <code>has_bad_digit</code> (a scan for the characters "024568") rejects the
overwhelming majority. The survivors have their rotations generated by string slicing -
<code>str_num[i:] + str_num[:i]</code> in Python, two sequential copy loops in C - and each
rotation is tested for primality. A subtle correctness detail: a rotation can numerically exceed
<code>max_limit</code> (rotating 199999 yields 999991), so any rotation above the sieve range is
rejected. That is safe, because such a value lies outside both the range I was asked to count and
the sieve, so it can never be a valid in-range circular prime.
</p>
<h4>External primesieve Library</h4>
<p>
The index-1 files keep the same digit-filter and rotation logic but replace the hand-rolled
sieve with the tuned
<a class="reference-source" href="https://github.com/kimwalisch/primesieve" rel="noopener noreferrer" target="_blank">primesieve</a>
library, which implements a fast segmented sieve in native code. The Python version
(<code>p0035_s1.py</code>) imports <code>primes</code> and gets back a list of primes up to the
limit. The C version (<code>p0035_s1.c</code>) calls <code>primesieve_generate_primes</code> to
obtain an array, then builds its own lookup array where <code>sieve[i] = 1</code> means
<em>prime</em> - the inverted polarity relative to the index-0 C sieve, so the rotation check
reads <code>rot > max_limit || !sieve[rot]</code>. The C version also allocates the lookup
array up to <code>max(max_limit, 1000000)</code>, a floor that keeps the small-limit cases
consistent. The algorithmic structure is otherwise identical; only prime generation is delegated
to a faster implementation.
</p>
</article>