柴柴柴拆柴柴 edited 5 年，6 月前
人们至今没有找到一个判断一个正整数是否为素数的简单方法，尽管
然而，这种方法计算量过大，因此在实务中通常使用
关于
在离散数学课程中，有这样一道作业：
给定一个整数
，求大于等于 的最小素数
已知相邻两个素数之差不会超过246
下面给出解决这个问题的Python代码：
import random
def fastmod(x,n,p):
res=1
while n!=0:
if n&1==1:
res=(res*x)%p
n>>=1
x=(x*x)%p
return res
def miller_rabin(n):
d=n-1
i=random.randint(1,n-1)
while d!=1:
if fastmod(i,d,n)==1:
if d%2!=0:
return True
d=d//2
if fastmod(i,d,n)==n-1:
return True
else:
return False
return True
r1=int(input("r1="));i=r1+1
while i<=r1+246:
if i%2!=0:
if miller_rabin(i):
res=i
break
i+=1
print(res)
支持
支持