Problem 35: Circular Primes

Project Euler Problem 35 Solution

EulerSolve provides an optimized solution for Project Euler Problem 35, Circular Primes, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary A circular prime is a prime number whose every cyclic digit rotation is also prime. If $n=197$, the rotations are $197$, $971$, and $719$, so 197 is circular. The task is to count all circular primes below $10^6$. The important counting detail is that the problem asks for individual primes, not rotation classes. Thus the orbit $\{197,971,719\}$ contributes 3, while 11 contributes 1 because its two rotations coincide numerically. Mathematical Approach Write a $k$-digit number as $n=d_0d_1\cdots d_{k-1}$. Circular primes are naturally described by the orbit generated by cyclically moving the leftmost digit to the end. The rotation orbit Define the one-step left rotation by $$R(d_0d_1\cdots d_{k-1})=d_1d_2\cdots d_{k-1}d_0.$$ Then $n$ is circular exactly when every member of the finite orbit $$\{n,R(n),R^2(n),\dots,R^{k-1}(n)\}$$ is prime. After $k$ rotations we return to the starting arrangement, so $R^k(n)=n$. The same rotation can be written arithmetically. If $n$ has $k$ digits and $P=10^{k-1}$, then $$R(n)=10\left(n \bmod P\right)+\left\lfloor \frac{n}{P} \right\rfloor.$$ Most orbits have size $k$, but repeated digits can shorten the orbit. For example, $11$ is fixed by rotation, so its orbit has size 1 even though it has two digits. Necessary digit constraints Suppose a circular prime has at least two digits....

Detailed mathematical approach

Problem Summary

A circular prime is a prime number whose every cyclic digit rotation is also prime. If $n=197$, the rotations are $197$, $971$, and $719$, so 197 is circular. The task is to count all circular primes below $10^6$.

The important counting detail is that the problem asks for individual primes, not rotation classes. Thus the orbit $\{197,971,719\}$ contributes 3, while 11 contributes 1 because its two rotations coincide numerically.

Mathematical Approach

Write a $k$-digit number as $n=d_0d_1\cdots d_{k-1}$. Circular primes are naturally described by the orbit generated by cyclically moving the leftmost digit to the end.

The rotation orbit

Define the one-step left rotation by

$$R(d_0d_1\cdots d_{k-1})=d_1d_2\cdots d_{k-1}d_0.$$

Then $n$ is circular exactly when every member of the finite orbit

$$\{n,R(n),R^2(n),\dots,R^{k-1}(n)\}$$

is prime. After $k$ rotations we return to the starting arrangement, so $R^k(n)=n$.

The same rotation can be written arithmetically. If $n$ has $k$ digits and $P=10^{k-1}$, then

$$R(n)=10\left(n \bmod P\right)+\left\lfloor \frac{n}{P} \right\rfloor.$$

Most orbits have size $k$, but repeated digits can shorten the orbit. For example, $11$ is fixed by rotation, so its orbit has size 1 even though it has two digits.

Necessary digit constraints

Suppose a circular prime has at least two digits. If one of its digits were in $\{0,2,4,5,6,8\}$, some rotation would place that digit in the units position. The rotated number would then be divisible by 2 or 5, so it could not be prime. Therefore every multi-digit circular prime must use only digits from

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

There is a second useful invariant: rotations preserve the sum of the digits. Hence they also preserve the residue modulo 3. If the digit sum were divisible by 3, then every rotation would be divisible by 3, so the only possible circular prime of that kind would be the single-digit prime 3 itself. This explains why circular primes are extremely sparse.

The provided implementations do not explicitly apply these filters, because a direct scan below one million is already fast enough. Still, these facts give the correct mathematical picture of why the brute-force search works so well.

Why the count is over primes, not over orbits

If one element of a rotation orbit is circular, then every element of the same orbit is circular, because they all have exactly the same set of rotations. The problem, however, does not ask for the number of distinct orbits. It asks for the number of circular primes themselves.

So the orbit $\{197,971,719\}$ contributes 3 to the answer, while the orbit $\{11\}$ contributes 1. This is precisely why the direct strategy of scanning every prime below the limit and testing it independently gives the right total.

Worked examples

For $197$, the orbit is

$$197 \to 971 \to 719 \to 197.$$

All three distinct values are prime, so each of them is a circular prime.

For $101$, the rotations are $101$, $011$, and $110$. Interpreted numerically, these are $101$, $11$, and $110$. Since $110$ is composite, 101 is not circular. This example shows both why a zero digit is fatal and why converting a rotated digit string back to an integer causes no ambiguity in the primality test.

Completing the full search below $10^6$ yields 55 circular primes.

How the Code Works

Precomputing primality

The C++, Python, and Java implementations begin by building a Sieve of Eratosthenes slightly beyond the requested search bound. That table lets the main loop answer most primality queries in constant time.

Checking the entire rotation orbit

Each implementation then scans upward through the integers below the limit and immediately skips any value that the sieve already marks as composite. For every remaining prime, it generates all cyclic rotations of the decimal representation and tests every rotated value for primality.

The three languages use different syntax for the rotation step, but mathematically they are doing the same thing: computing $n,R(n),\dots,R^{k-1}(n)$ and requiring all of them to be prime. When a rotated value lies inside the sieve table, the implementation reads the answer directly from the table.

If a user reuses the same programs with a smaller custom bound, a rotation can land beyond the sieve range even though the original number is below the limit. In that case the implementations fall back to ordinary trial division, which preserves correctness for general bounds. For the Project Euler target $10^6$, every rotation still has at most six digits, so the sieve usually handles the whole job.

Sanity checks

Before reporting the final total, the programs verify two small checkpoints: 197 must be recognized as circular, and the number of circular primes below 100 must be 13. Those checks match the mathematics exactly and guard against mistakes in the rotation logic.

Complexity Analysis

If the search limit is $L$, building the sieve costs $O(L \log\log L)$ time and $O(L)$ space. After that, only prime candidates survive the first filter, so the outer scan effectively visits $\pi(L)$ numbers.

For a $k$-digit prime, the literal implementations construct $k$ rotated strings and convert them back to integers, so the orbit check is $O(k^2)$ character-level work in the straightforward string model. Under the Project Euler bound $L=10^6$, we always have $k \le 6$, so this is a tiny constant. In practice the runtime is dominated by the sieve and a short scan over the roughly $78{,}498$ primes below one million.

Footnotes and References

Problem page: Project Euler 35
Circular primes: Wikipedia - Circular prime
Prime numbers: Wikipedia - Prime number
Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes
Cyclic permutation: Wikipedia - Cyclic permutation

Problem 35 source code

C++

#include <cmath>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>

namespace {

struct Options {
    int limit = 1000000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (const char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 2;
}

std::vector<bool> prime_sieve(const int limit) {
    std::vector<bool> prime(static_cast<std::size_t>(limit + 1), true);
    if (limit >= 0) {
        prime[0] = false;
    }
    if (limit >= 1) {
        prime[1] = false;
    }
    for (int p = 2; p <= limit / p; ++p) {
        if (!prime[static_cast<std::size_t>(p)]) {
            continue;
        }
        for (int q = p * p; q <= limit; q += p) {
            prime[static_cast<std::size_t>(q)] = false;
        }
    }
    return prime;
}

bool is_prime_trial(const int n) {
    if (n < 2) {
        return false;
    }
    if ((n % 2) == 0) {
        return n == 2;
    }
    for (int p = 3; p <= n / p; p += 2) {
        if ((n % p) == 0) {
            return false;
        }
    }
    return true;
}

bool is_circular_prime(const int n, const std::vector<bool>& sieve) {
    std::string s = std::to_string(n);

    for (std::size_t shift = 0; shift < s.size(); ++shift) {
        std::rotate(s.begin(), s.begin() + 1, s.end());
        const int rot = std::stoi(s);

        bool prime = false;
        if (rot < static_cast<int>(sieve.size())) {
            prime = sieve[static_cast<std::size_t>(rot)];
        } else {
            prime = is_prime_trial(rot);
        }
        if (!prime) {
            return false;
        }
    }

    return true;
}

int solve(const int limit) {
    const auto sieve = prime_sieve(limit + 100);

    int count = 0;
    for (int n = 2; n < limit; ++n) {
        if (!sieve[static_cast<std::size_t>(n)]) {
            continue;
        }
        if (is_circular_prime(n, sieve)) {
            ++count;
        }
    }

    return count;
}

bool run_checkpoints() {
    const auto sieve = prime_sieve(1000);
    if (!is_circular_prime(197, sieve)) {
        std::cerr << "Checkpoint failed for 197" << '\n';
        return false;
    }
    if (solve(100) != 13) {
        std::cerr << "Checkpoint failed for limit=100" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.limit) << '\n';
    return 0;
}

Python

import sys
from math import isqrt

def prime_sieve(limit):
    """Generate a boolean list where sieve[i] is True if i is prime."""
    sieve = [True] * (limit + 1)
    if limit >= 0:
        sieve[0] = False
    if limit >= 1:
        sieve[1] = False
    
    for p in range(2, isqrt(limit) + 1):
        if sieve[p]:
            for q in range(p * p, limit + 1, p):
                sieve[q] = False
    
    return sieve

def is_prime_trial(n):
    """Trial division primality test for large numbers."""
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    
    for p in range(3, isqrt(n) + 1, 2):
        if n % p == 0:
            return False
    return True

def is_circular_prime(n, sieve):
    """Check if all rotations of n are prime."""
    s = str(n)
    
    for _ in range(len(s)):
        # Rotate the string
        s = s[1:] + s[0]
        rot = int(s)
        
        # Check primality using sieve if possible, otherwise trial division
        if rot < len(sieve):
            prime = sieve[rot]
        else:
            prime = is_prime_trial(rot)
        
        if not prime:
            return False
    
    return True

def solve(limit):
    """Count circular primes below limit."""
    # Generate sieve with extra buffer for rotations
    sieve = prime_sieve(limit + 100)
    
    count = 0
    for n in range(2, limit):
        if not sieve[n]:
            continue
        if is_circular_prime(n, sieve):
            count += 1
    
    return count

def run_checkpoints():
    """Run verification checkpoints."""
    sieve = prime_sieve(1000)
    
    if not is_circular_prime(197, sieve):
        print("Checkpoint failed for 197", file=sys.stderr)
        return False
    
    if solve(100) != 13:
        print("Checkpoint failed for limit=100", file=sys.stderr)
        return False
    
    return True

def parse_arguments(args):
    """Parse command line arguments."""
    options = {
        'limit': 1000000,
        'run_checkpoints': True
    }
    
    i = 1
    while i < len(args):
        arg = args[i]
        
        if arg == '--skip-checkpoints':
            options['run_checkpoints'] = False
        elif arg.startswith('--limit='):
            try:
                value_str = arg[8:]
                if not value_str:
                    print("Unknown argument: " + arg, file=sys.stderr)
                    return None
                options['limit'] = int(value_str)
            except ValueError:
                print("Unknown argument: " + arg, file=sys.stderr)
                return None
        else:
            print("Unknown argument: " + arg, file=sys.stderr)
            return None
        
        i += 1
    
    if options['limit'] < 2:
        print("Limit must be at least 2", file=sys.stderr)
        return None
    
    return options

def main():
    """Main entry point."""
    args = sys.argv[1:]
    
    options = parse_arguments(args)
    if options is None:
        return 1
    
    if options['run_checkpoints'] and not run_checkpoints():
        return 2
    
    result = solve(options['limit'])
    print(result)

if __name__ == '__main__':
    main()

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Euler35 {

    private static class Options {
        int limit = 1000000;
        boolean runCheckpoints = true;
    }

    private static boolean parseArguments(String[] args, Options options) {
        for (String arg : args) {
            if (arg.equals("--skip-checkpoints")) {
                options.runCheckpoints = false;
                continue;
            }
            if (arg.startsWith("--limit=")) {
                String tail = arg.substring("--limit=".length());
                if (tail.isEmpty()) {
                    System.err.println("Invalid limit format");
                    return false;
                }
                try {
                    options.limit = Integer.parseInt(tail);
                    continue;
                } catch (NumberFormatException e) {
                    System.err.println("Invalid limit format");
                    return false;
                }
            }
            System.err.println("Unknown argument: " + arg);
            return false;
        }
        return options.limit >= 2;
    }

    private static boolean[] primeSieve(int limit) {
        boolean[] prime = new boolean[limit + 1];
        for (int i = 2; i <= limit; i++) {
            prime[i] = true;
        }
        for (int p = 2; p * p <= limit; p++) {
            if (prime[p]) {
                for (int q = p * p; q <= limit; q += p) {
                    prime[q] = false;
                }
            }
        }
        return prime;
    }

    private static boolean isPrimeTrial(int n) {
        if (n < 2) return false;
        if (n % 2 == 0) return n == 2;
        for (int p = 3; p * p <= n; p += 2) {
            if (n % p == 0) return false;
        }
        return true;
    }

    private static boolean isCircularPrime(int n, boolean[] sieve) {
        String s = String.valueOf(n);
        int len = s.length();
        for (int shift = 0; shift < len; shift++) {
            String rotated = s.substring(shift) + s.substring(0, shift);
            int rot = Integer.parseInt(rotated);
            boolean isPrime;
            if (rot < sieve.length) {
                isPrime = sieve[rot];
            } else {
                isPrime = isPrimeTrial(rot);
            }
            if (!isPrime) {
                return false;
            }
        }
        return true;
    }

    private static int solve(int limit) {
        boolean[] sieve = primeSieve(limit + 100);
        int count = 0;
        for (int n = 2; n < limit; n++) {
            if (!sieve[n]) continue;
            if (isCircularPrime(n, sieve)) {
                count++;
            }
        }
        return count;
    }

    private static boolean runCheckpoints() {
        boolean[] sieve = primeSieve(1000);
        if (!isCircularPrime(197, sieve)) {
            System.err.println("Checkpoint failed for 197");
            return false;
        }
        if (solve(100) != 13) {
            System.err.println("Checkpoint failed for limit=100");
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Options options = new Options();
        if (!parseArguments(args, options)) {
            System.exit(1);
        }
        if (options.runCheckpoints && !runCheckpoints()) {
            System.exit(2);
        }
        System.out.println(solve(options.limit));
    }
}