(No Ratings Yet)

## Project Euler Problem 35 Solution

#### 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 (primes35.txt) and included those below 1 million (78,498 primes) 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 (1,113 primes).

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") # primes35.txt is a list of prime numbers < 1,000,000 or die "File 'primes35.txt' not found";   my %is_prime = map { (\$_*1,1) } grep length(\$_)==2 || !/[024568]/, <IN>; my \$cp = 0; @x=keys %is_prime;   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";   sub rotate { @_[0]=~s/(\d)(\d+)/\2\1/ }```

• The next circular prime is a rep unit 19 digits long (R19 = 1111111111111111111), so using this method for finding circular primes > 1,000,000 is impracticable
• OEIS A016114

## Discussion

### 3 Responses to “Project Euler Problem 35 Solution”

1. Great explanation! Thank you.

Posted by Tarren | April 9, 2009, 3:36 AM
```from Euler import prime_sieve, is_prime   def circular (n): circ = [] n = str(n) for i in range(len(n)): circ.append(int(n[1:]+n[0])) n = n[1:]+n[0] return circ   def is_prime_list (List): for i in List: if not is_prime(i): return False return True     primes = prime_sieve(1000000) circ = [] for i in primes: if (is_prime_list(circular(i))): circ.append(i)   print "Answer to PE35 = " + str(len(circ))```