princeofsudan

ProjectEuler#35 Circular primes

Mar 20th, 2013
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.95 KB | None | 0 0
  1. #The number, 197, is called a circular prime because all rotations of the
  2. #digits: 197, 971, and 719, are themselves prime.
  3.  
  4. #There are thirteen such primes below 100:
  5. #2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
  6.  
  7. #How many circular primes are there below one million?
  8.  
  9. def isPrime(n):
  10.     '''check if integer n is a prime'''
  11.     # range starts with 2 and only needs to go up the square-root of n
  12.     for x in range(2, int(n**0.5)+1):
  13.         if n % x == 0:
  14.             return False
  15.     return True
  16.  
  17. def isCirPrime(n):
  18.     '''check if integer n is a circular prime'''
  19.     if n < 10:
  20.         return True
  21.     nstr = str(n)
  22.     for i in range(len(nstr)-1):
  23.         nstr = nstr[1:]+nstr[0]
  24.         if not isPrime(int(nstr)):
  25.             return False
  26.     return True
  27.  
  28. cirPrimes = [2]
  29.  
  30. for i in range(3,1000000,2): #Checks only odd numbers for prime
  31.     if isPrime(i) and isCirPrime(i):
  32.         cirPrimes.append(i)
  33.  
  34. print len(cirPrimes)
Advertisement
Add Comment
Please, Sign In to add comment