python中素数_素数判断算法(基于python实现)

发布于:2021-10-26 19:46:28

素数是只能被1与自身整除的数,根据定义,我们可以实现第一种算法。


算法一:


defisprime(n):if n < 2: returnFalsefor i in range(2,int(math.sqrt(n))+1):if n % i ==0:returnFalsereturn True


任意一个合数都可分解为素数因子的乘积,观察素数的分布可以发现:除 2,3 以外的素数必定分布在 6k (k为大于1的整数) 的两侧。6k % 6 == 0, (6k+2) % 2== 0,(6k+3) %3==0,(6k+4)%2==0,


所以2,3外的素数形式只能写成 6k+1 或 6k-1的形式。据此,我们可以缩小因子范围。


算法二:


def isprime(n):


if n == 2 or n == 3:


return True


if n % 2 == 0 or n % 3 == 0:


return False


for k in range(6,int(math.sqrt(n)) + 2, 6):


if n % (k-1) == 0 or n % (k+1) == 0:


return False


return True


建立一个大小为n的数组,初始值置为真。从2开始设置步长(length)直至n的*方根,将length*i (i > 1) 的值置为False。这就是埃拉托斯特尼筛法的基本思想。适用于筛选小于n的所有素数,算法如下:


算法三:


defisprime(n):


r= [[i,True] for i in range(1,n+1)]


r[0]= [1,False]for i in range(1,int(math.sqrt(n))):


j= i * 2 + 1


while j


r[j]= [j+1,False]


j+= i + 1


return r


费马小定理: ap-1= 1 (mod p) ,其中gcd(p,a) = 1 且 p 为素数


p为素数时等式一定成立,但使等式成立的p不一定都是素数,但非素数p数量极少,称之为伪素数。


任意大素数n可写成 n = u * 2t + 1, 其中 t 为 大于1 的整数,u为奇数。an - 1 = (au)2^t, 求出au 后,连续t次*方即可求得。


算法四:


defisprime_fourth(n):if n == 2: returnTrueif n % 2 == 0: returnFalse#若n为大于2的素数,形式可写成 n=u*(2^t) + 1, t >= 1 and u % 2 == 1


t =0


u= n - 1


while u % 2 ==0:


t+= 1u//= 2


#随机选择底数,若n为素数,gcd(a,n)==1


a = random.randint(2,n-1)#若n为素数,则a^(n-1) % n == 1;先计算 a^u % n,再连续t次*方可得


r =pow(a,u,n)if r != 1:while t > 1 and r != n-1:


r= (r*r) %n


t-= 1


if r != n - 1:returnFalsereturn True

相关推荐

最新更新

猜你喜欢