Problem Description

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?

Analysis

We used our file of prime numbers and included those below 1 million and excluded those greater than 10 that contained the digits {0, 2, 4, 5, 6 or 8} because as a prime is rotated it cannot end with any of these digits and remain prime.

We read these numbers into a hash (associative array) using the prime numbers as keys. The hash also serves as an ‘is prime?’ function. If a particular key exists then the number is prime and if it does not, then it’s composite. The program loops through the hash’s keys and checks each rotation as a prime number. When every rotation is prime it’s counted as a circular prime.

Solution

Runs < 1 second in Perl.

open (IN,"<primes35.txt")  or die "Error opening file: $!";
my %is_prime = map { ($_*1,1) } grep length($_)==2 || !/[024568]/, <IN>;
my $cp = 0;
 
P: for my $prime (keys %is_prime) {
      for ( 2..length($prime) )  { 
        rotate($prime); 
        next P unless $is_prime{$prime} 
     }
     $cp++;
  }
print "Answer to PE35 = $cp";

Comments

• Check out the tools post for an explanation of the rotate() function
• The next circular prime is a rep unit 19 digits long (R₁₉ = 1111111111111111111), so using this method for finding circular primes > 1,000,000 is impracticable
• OEIS A016114