The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime. There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97. How many circular primes are there below one million?

At first I thought circular primes were any permutation of the prime, but then 791 would be in the example as well, so I realised that it is primes that you can rotate such that any rotation is also a prime. There is a long article on different groups of prime numbers at Wikipedia called List of prime numbers. That includes circular primes, so for the lazy reader, you can go there and count them instead of programming the solution.

I must admit that I don’t think I have found a very nice solution, but it runs fast enough to satisfy me. It is a brute force algorithm where we search every prime below 1.000.000 to see if it can be rotated.

Circular primes have two characteristics we will use to speed up the search for all the circular primes.  If it contains an even number or 5 then at some point in the cycle we will encounter a number which is not a prime and thus the number we are investigating is not a circular prime. There are two exceptions to this rule, the primes 2 and 5 are indeed primes even if they follow the rule of containing an even number or five.

The Algorithm

I assume that I have a list of all primes below 1.000.000 for this. This can rather easily be done with a Sieve of Eratosthenes which we built in Problem 10.

1. Take the first number in the list.
2. Check if it contains even numbers or five. If not continue to 3. Otherwise discard it and go to 1.
3. Move the number to a temporary list.
4. Rotate the number and check if it is a prime. If not discard the temporary list and go to 1.
5. If the number is in the prime list move it to the temporary list.
6. if the number is in the temporary list do nothing.
7. if all rotations are not checked go to 4.
8. return the length of the temporary list.

This is the algorithm I wrote in order to find the circular primes.

My main philosophy was to stop as soon as I found a number which was not a prime and then remove all the prime numbers already found in  that cycle. The reason I wanted to stop as soon as I encountered a non-prime is that I expect that there are far more candidates than actual circular primes, so I would do a lot more work checking all the cycles to full length.

public int CheckCircularPrimes(int prime){

    int multiplier = 1;

    int number = prime;

    int count = 0;

    int d;

 

    //Count the digits and check for even numbers

    while (number > 0) {

        d = number % 10;

        if (d % 2 == 0 || d == 5) {

            primes.Remove(prime);

                return 0;

            }

            number /= 10;

            multiplier *= 10;

            count++;

    }

    multiplier /= 10;

 

    //Rotate the number and check if they are prime

    number = prime;

    List foundCircularPrimes = new List();

 

    for (int i = 0; i < count; i++) {

        if(primes.Contains(number)) {

            foundCircularPrimes.Add(number);

            primes.Remove(number);

        }else if(!foundCircularPrimes.Contains(number)) {

            return 0;

        }

 

        d = number % 10;

        number = d * multiplier + number / 10;

    }

 

    return foundCircularPrimes.Count;

}

The primes list is a SortedSet I have made as an object variable. The main loop of the algorithm looks like

int noCircularPrimes = 2;

primes = new SortedSet<int>(ESieve(1000000));

//Special cases

primes.Remove(2);

primes.Remove(5);

 

while (primes.Count > 0) {

    noCircularPrimes += CheckCircularPrimes(primes.Min);

}

Even though I don’t really think that it is a nice solution the result of running it is

The number of circular primes below 1.000.000 is 55

Solution took 80 ms