Project Euler Problem 35

Solution

Answer: 55

1. Mathematical analysis

A circular prime is a prime number such that every cyclic rotation of its digits is also prime.

For example:

$$197 \to 971 \to 719$$

All three are prime, so $197$ is circular.

We want to count all circular primes below $10^6$.

Key insight 1: Rotations

If a number has digits $d_1d_2\dots d_k$, then its rotations are formed by moving leading digits to the end.

For example:

$$197 \to 971 \to 719$$

Algorithmically:

Convert number to string.
Rotate:
"197" → "971"
"971" → "719"
Convert back to integers.

A number is circular prime iff all rotations are prime.

Key insight 2: Digit elimination

For numbers with more than one digit:

If any digit is:

$$0,2,4,5,6,8$$

then some rotation will end in an even digit or $5$, making it composite.

Example:

$$23 \to 32$$

$32$ is even → not prime.

Example:

$$157 \to 571 \to 715$$

$715$ ends in $5$ → composite.

So, except for the single-digit primes $2$ and $5$, every circular prime must use only digits:

$${1,3,7,9}$$

This drastically reduces the search space.

Key insight 3: Fast primality testing

We need many prime checks, so the best method is the Sieve of Eratosthenes.

We generate all primes below one million:

Create boolean array of primality.
Mark multiples of each prime as composite.
Prime lookup becomes $O(1)$.

Time complexity:

$$O(n \log\log n)$$

for the sieve, with cheap rotation checks afterward.

Algorithm

Build a prime sieve up to $10^6$.
For each prime:

Generate all digit rotations.
Check whether every rotation is prime.

Count valid numbers.

Optimization:

Skip numbers containing forbidden digits $0,2,4,5,6,8$ (except $2,5$).

2. Python implementation

def count_circular_primes(limit):
    # Build sieve of Eratosthenes
    sieve = [True] * limit
    sieve[0] = sieve[1] = False

    for i in range(2, int(limit ** 0.5) + 1):
        if sieve[i]:
            # Mark multiples as composite
            for j in range(i * i, limit, i):
                sieve[j] = False

    def rotations(n):
        """Generate all cyclic rotations of n."""
        s = str(n)
        return [int(s[i:] + s[:i]) for i in range(len(s))]

    circular_count = 0

    for n in range(2, limit):
        if not sieve[n]:
            continue

        # Skip impossible candidates
        if n > 10 and any(d in "024568" for d in str(n)):
            continue

        # Check all rotations
        if all(sieve[r] for r in rotations(n)):
            circular_count += 1

    return circular_count

# Compute answer
print(count_circular_primes(1_000_000))

3. Code walkthrough

Sieve construction

sieve = [True] * limit
sieve[0] = sieve[1] = False

We assume all numbers are prime initially, except $0$ and $1$.

for i in range(2, int(limit ** 0.5) + 1):

We only need to sieve up to:

$$\sqrt{n}$$

because every composite has a factor ≤ its square root.

for j in range(i * i, limit, i):
    sieve[j] = False

Mark multiples of each prime as composite.

Starting at $i^2$ is sufficient because smaller multiples were already handled.

Rotation generation

def rotations(n):
    s = str(n)
    return [int(s[i:] + s[:i]) for i in range(len(s))]

Example:

For $197$:

$i=0$: "197"
$i=1$: "971"
$i=2$: "719"

Result:

$$[197,971,719]$$

Digit pruning

if n > 10 and any(d in "024568" for d in str(n)):
    continue

This skips impossible cases.

Example:

$23$ skipped because of digit $2$
$101$ skipped because of digit $0$

This greatly speeds up the search.

Circularity test

if all(sieve[r] for r in rotations(n)):

Checks every rotation instantly using the sieve.

Small-example verification

Below $100$, the program returns exactly:

$$2,3,5,7,11,13,17,31,37,71,73,79,97$$

There are:

$$13$$

which matches the problem statement.

4. Final verification

Sanity checks:

We correctly include single-digit primes $2,3,5,7$.
We exclude trivial non-primes generated by rotations ending in even digits or $5$.
Verified against the known count below $100$ (=13).
The accepted Project Euler value is known to be modest (not thousands), and our result falls in the expected range.

Answer: 55