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.
Using python sets, the sieve of Eratosthenes from problem 10 and some pre-filtering for primes with even digits.
# sieve of Eratosthenes def sieve(n): primes = range(2,n) x = 0 while primes[x] < n**0.5: # remove all multiples of the current prime from primes primes = [y for y in primes if y==primes[x] or y%primes[x]] x = x+1 return primes def get_rotations(x): strx = str(x) rotations = [strx[i:] + strx[:i] for i in range(len(strx))] rotations = map(int,rotations) return rotations def all_digits_odd(n): n = str(n) for digit in n: if int(digit) % 2 == 0: return False return True @print_timing def num_circular_primes(x): primes = sieve(x) # optimize: remove all primes with any even digits primes = filter(all_digits_odd,primes) primes = set(primes) cprimes = 0 max_prime = max(primes) for p in primes: rotations = set(get_rotations(p)) intersection = primes & rotations # if all rotations are primes, they are all circular if len(intersection) == len(rotations): cprimes += len(intersection) #remove all the rotations from the working set primes = primes - rotations return cprimes >>> num_circular_primes(1000000) num_circular_primes took 6531.000 ms 54 |