【python】---- 查找兩個數之間的【可逆素數】

1. 問題背景

輸入正整數m,n，查找[m,n]區間的可逆素數。

可逆素數：可逆素數是指該數本身是一個素數，并且把該數倒過來也是一個素數。

例如：

1009是一個素數，把它倒過來9001也是一個素數，是以我們就說1009是一個可逆素數（同理9001也是一個可逆素數）。

2. 判斷是不是素數

1. 方法一：

最簡單的方法，依次除以【從2到數字本身（不包括本身）】，不存在餘數是0的數，就是素數；

思路清晰，但是效率低，比如：

假如 n 是合數，必然存在非1的兩個約數 p1 和 p2 ，其中p1<= math.sqrt(n)，p2>= math.sqrt(n)。
能被4整除的，肯定能被2整除；能被6整除的肯定能被3整除！

def isPrime(num):
  num = int(num)
  if (num <= 3):
    return num > 1
  for i in range(2,num):
    if(num % i == 0):
      return False
  return True

複制

2. 方法二：

去掉 math.sqrt(n)以後的數。

import math
def isPrime(num):
  num = int(num)
  if (num <= 3):
    return num > 1
  sqrt = int(math.sqrt(num)) + 1
  for i in range(2,sqrt):
    if(num % i == 0):
      return False
  return True

複制

3. 方法三：參考百度素數計算

去掉能被2，3，5整除的數。

import math
def isPrime(num):
  num = int(num)
  if (num <= 3):
    return num > 1
  elif(num % 2 == 0 or num % 3 == 0):
    return False
  elif(num % 6 != 1 and num % 6 != 5):
    return False
  sqrt = int(math.sqrt(num)) + 1
  for i in range(5,sqrt,6):
    if(num % i == 0 or num % (i + 2) == 0):
      return False
  return True

複制

3. 判斷是不是可逆素數

def isReversiblePrime(num):
  num = str(num)
  nums = list(num)
  nums.reverse()
  onum = ''.join(nums)
  if(isPrime(num) and isPrime(onum)):
    return True
  else:
    False

複制

4. 完整代碼

import math
def isPrime(num):
  num = int(num)
  if (num <= 3):
    return num > 1
  elif(num % 2 == 0 or num % 3 == 0):
    return False
  elif(num % 6 != 1 and num % 6 != 5):
    return False
  sqrt = int(math.sqrt(num)) + 1
  for i in range(5,sqrt,6):
    if(num % i == 0 or num % (i + 2) == 0):
      return False
  return True

def isReversiblePrime(num):
  num = str(num)
  nums = list(num)
  nums.reverse()
  onum = ''.join(nums)
  if(isPrime(num) and isPrime(onum)):
    return True
  else:
    False

if __name__ == "__main__":
  m = int(input('請輸入查找【可逆素數】的開始數：'))
  n = int(input('請輸入查找【可逆素數】的結束數：'))
  if(m < n):
    for i in range(m,n):
      if(isReversiblePrime(i)):
        print(i)

複制

5. 預覽