柴柴柴拆柴柴 edited 5 年，3 月前
人们至今没有找到一个判断一个正整数是否为素数的简单方法，尽管$\mathrm{Wilson}$定理给出了一个正整数是素数的充要条件，即正整数$n$是素数当且仅当
$$(n-1)! \equiv -1 \; (\mathrm{mod} \; n)$$
然而，这种方法计算量过大，因此在实务中通常使用$\mathrm{Miller-Rabin}$算法进行素性测试，这是一个随机算法，理论依据是费马小定理与二次探测定理。
关于$\mathrm{Miller-Rabin}$算法的细节，可以访问此链接。
在离散数学课程中，有这样一道作业：
给定一个整数$n$，求大于等于$n$的最小素数
已知相邻两个素数之差不会超过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)
支持
支持