Senseye

Prime number palindrome Python

Sep 28th, 2018
135
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import time, math
  2.  
  3. # Max possible result, all 10-digits palindromes % 11 == 0
  4. MAX = 999999999
  5.  
  6.  
  7. def get_primes(start, finish):
  8.     variants = [True] * finish
  9.  
  10.     limit = int(math.ceil(math.sqrt(finish)))
  11.  
  12.     for i in xrange(2, limit):
  13.         if variants[i]:
  14.             for j in xrange(i * i, finish, i):
  15.                 variants[j] = False
  16.  
  17.     result = []
  18.     for i in xrange(start, finish):
  19.         if variants[i]:
  20.             result.append(i)
  21.  
  22.     return result
  23.  
  24.  
  25. def is_palindrome(value):
  26.     digits = [0, 0, 0, 0, 0, 0, 0, 0, 0]
  27.  
  28.     i = 0
  29.     while value > 0:
  30.         digits[i] = value % 10
  31.  
  32.         value //= 10
  33.  
  34.         i += 1
  35.  
  36.     limit = i >> 1
  37.     end = i - 1
  38.  
  39.     for j in xrange(0, limit + 1):
  40.         if digits[j] != digits[end - j]:
  41.             return False
  42.  
  43.     return True
  44.  
  45.  
  46. def find():
  47.     primes = get_primes(10000, 99999)
  48.  
  49.     size = len(primes)
  50.  
  51.     result = (0, 0, 0)
  52.  
  53.     for i in xrange(0, size):
  54.         for j in xrange(i + 1, size):
  55.             left = primes[i]
  56.             right = primes[j]
  57.  
  58.             possible = left * right
  59.  
  60.             if possible > MAX:
  61.                 break
  62.  
  63.             if possible > result[0] and is_palindrome(possible):
  64.                 result = (possible, left, right)
  65.  
  66.     return result
  67.  
  68.  
  69. start_time = time.time()
  70.  
  71. result = find()
  72.  
  73. end_time = time.time()
  74.  
  75. print("Palindrome %d" % result[0])
  76. print("Prime numbers %d * %d" % (result[1], result[2]))
  77. print("Duration %s" % (end_time - start_time))
RAW Paste Data