提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Python

当前栏目

【python】---- 查找两个数之间的【可逆素数】

Python
2023-04-18 17:00:16 时间

1. 问题背景

输入正整数m,n，查找[m,n]区间的可逆素数。

可逆素数：可逆素数是指该数本身是一个素数，并且把该数倒过来也是一个素数。

例如： 1009是一个素数，把它倒过来9001也是一个素数，所以我们就说1009是一个可逆素数（同理9001也是一个可逆素数）。

2. 判断是不是素数

1. 方法一：

最简单的方法，依次除以【从2到数字本身（不包括本身）】，不存在余数是0的数，就是素数；

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

  1. 假如 n 是合数，必然存在非1的两个约数 p1 和 p2 ，其中p1<= math.sqrt(n)，p2>= math.sqrt(n)。
  2. 能被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. 预览

相关文章