Finding Circular Primes: A Journey Through Project Euler Problem 35

I recently tackled Project Euler's Problem 35, which asks: how many circular primes exist below one million? A circular prime is a prime number that remains prime under all rotations of its digits. For example, 197 is a circular prime because 197, 971, and 719 are all prime.

The Approach

My solution breaks down into three main steps:

1. Generate all primes below one million

I used a straightforward trial division method to test each number for primality, storing valid primes in a list for quick lookup.

2. Test each prime for circularity

For each prime, I used Python's collections.deque to rotate the digits. A deque (double-ended queue) makes rotation elegant—just call rotate(1) to shift all digits one position to the left.

3. Verify all rotations are prime

I checked whether each rotation exists in my pre-generated prime list. Only if all rotations are prime does the original number qualify as a circular prime.

The Solution

Here's the complete code:

python

import math
import collections

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

prime_numbers = []
circular_primes = []

for i in range(0, 1000000):
    if is_prime(i):
        prime_numbers.append(i)

for prime_number in prime_numbers:
    pn2 = collections.deque(str(prime_number))
    pn3 = collections.deque(str(prime_number))
    pn4 = collections.deque(str(prime_number))
    pn5 = collections.deque(str(prime_number))
    pn6 = collections.deque(str(prime_number))
    
    if len(str(prime_number)) == 1:
        circular_primes.append(prime_number)
    
    if len(str(prime_number)) == 2:
        pn2.rotate(1)
        one_rotation = int(''.join(pn2))
        if one_rotation in prime_numbers:
            circular_primes.append(prime_number)
    
    if len(str(prime_number)) == 3:
        pn3.rotate(1)
        one_rotation3 = int(''.join(pn3))
        if one_rotation3 in prime_numbers:
            pn3.rotate(1)
            two_rotation3 = int(''.join(pn3))
            if two_rotation3 in prime_numbers:
                circular_primes.append(prime_number)
    
    if len(str(prime_number)) == 4:
        pn4.rotate(1)
        one_rotation4 = int(''.join(pn4))
        if one_rotation4 in prime_numbers:
            pn4.rotate(1)
            two_rotation4 = int(''.join(pn4))
            if two_rotation4 in prime_numbers:
                pn4.rotate(1)
                three_rotation4 = int(''.join(pn4))
                if three_rotation4 in prime_numbers:
                    circular_primes.append(prime_number)
    
    if len(str(prime_number)) == 5:
        pn5.rotate(1)
        one_rotation5 = int(''.join(pn5))
        if one_rotation5 in prime_numbers:
            pn5.rotate(1)
            two_rotation5 = int(''.join(pn5))
            if two_rotation5 in prime_numbers:
                pn5.rotate(1)
                three_rotation5 = int(''.join(pn5))
                if three_rotation5 in prime_numbers:
                    pn5.rotate(1)
                    four_rotation5 = int(''.join(pn5))
                    if four_rotation5 in prime_numbers:
                        circular_primes.append(prime_number)
    
    if len(str(prime_number)) == 6:
        pn6.rotate(1)
        one_rotation6 = int(''.join(pn6))
        if one_rotation6 in prime_numbers:
            pn6.rotate(1)
            two_rotation6 = int(''.join(pn6))
            if two_rotation6 in prime_numbers:
                pn6.rotate(1)
                three_rotation6 = int(''.join(pn6))
                if three_rotation6 in prime_numbers:
                    pn6.rotate(1)
                    four_rotation6 = int(''.join(pn6))
                    if four_rotation6 in prime_numbers:
                        pn6.rotate(1)
                        five_rotation6 = int(''.join(pn6))
                        if five_rotation6 in prime_numbers:
                            circular_primes.append(prime_number)

print(len(circular_primes))

How It Works

The code handles numbers of different lengths separately. For a 3-digit number like 197:

• First rotation: 971

• Second rotation: 719

• If both are prime, 197 is circular

I extended this pattern up to 6-digit numbers, which covers all primes below one million.

What I Learned

This problem reinforced the value of preprocessing. By generating all primes once upfront, I converted what could have been expensive primality checks during rotation into simple list lookups. The deque data structure also proved perfect for digit rotation—sometimes the right tool makes all the difference.

The final answer? There are 55 circular primes below one million.