Problem 035

Project Euler

Circular primes

Problem 35

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?

First of all, except 2, there can be no other circular prime contains any even number. Also, for every circular prime found with x digits, there at most x-1 other circular prime found unless there are duplicate digits within the circular prime.

Starting with a list of prime numbers (by now, finding all prime under a million should be quite familiar if the problems are done in sequence), record 2 as circular prime since it is a special case and then go through each subsequent prime by checking if any of them contain an even digit, check if the number is still prime after rotating a single digit, and record all of the corresponding circular prime once a circular prime is found.