Problem Analysis
A circular prime 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.
The first is a divisibility
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
Sieve of Eratosthenes,
which marks all composites up to a limit n 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).
Solution Approach
Hand-rolled Sieve (Eratosthenes in C, Sundaram in Python)
Both index-0 files build their own sieve, then apply the digit filter and rotation check. The C
version (p0035_s0.c) uses a classic
Sieve of Eratosthenes
over a calloc-zeroed byte array where sieve[i] = 1 means composite. It
iterates i from 2 up to sqrt(max_num), and for each prime marks
multiples starting at i*i - everything smaller has already been marked by a smaller
factor, so this avoids redundant work. The Python version (p0035_s0.py) uses a
Sieve of Sundaram:
it marks integers of the form i + j + 2*i*j as composite, then each unmarked index
k maps to the odd prime 2k+1, 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.
Having the primes, both iterate over them. Single-digit primes are counted immediately. For
larger primes, has_bad_digit (a scan for the characters "024568") rejects the
overwhelming majority. The survivors have their rotations generated by string slicing -
str_num[i:] + str_num[:i] in Python, two sequential copy loops in C - and each
rotation is tested for primality. A subtle correctness detail: a rotation can numerically exceed
max_limit (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.
External primesieve Library
The index-1 files keep the same digit-filter and rotation logic but replace the hand-rolled
sieve with the tuned
primesieve
library, which implements a fast segmented sieve in native code. The Python version
(p0035_s1.py) imports primes and gets back a list of primes up to the
limit. The C version (p0035_s1.c) calls primesieve_generate_primes to
obtain an array, then builds its own lookup array where sieve[i] = 1 means
prime - the inverted polarity relative to the index-0 C sieve, so the rotation check
reads rot > max_limit || !sieve[rot]. The C version also allocates the lookup
array up to max(max_limit, 1000000), a floor that keeps the small-limit cases
consistent. The algorithmic structure is otherwise identical; only prime generation is delegated
to a faster implementation.