【python】---- 查找两个数之间的【可逆素数】
【python】---- 查找两个数之间的【可逆素数】
Rattenking
发布于 2022-01-06 20:16:46
发布于 2022-01-06 20:16:46
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 True2. 方法二：
去掉 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 True3. 方法三：参考百度素数计算
去掉能被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 True3. 判断是不是可逆素数
def isReversiblePrime(num):
num = str(num)
nums = list(num)
nums.reverse()
onum = ''.join(nums)
if(isPrime(num) and isPrime(onum)):
return True
else:
False4. 完整代码
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. 预览
在这里插入图片描述
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-12-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录