python质数怎么判断

判断质数的方法有很多种，以下列举几种用Python实现的方法，并为大家举例分析：

试除法是最简单的判断质数的方法，即从2开始逐一除以小于等于它一半的整数，如果都无法整除，则该数为质数。用Python实现如下：

defis_prime(n):

ifn=1:#小于等于1的数都不是质数

returnFalse

foriinrange(2,n//2+1):#试除2到n/2的整数

ifn%i==0:#如果n能被i整除，则n不是质数

returnFalse

returnTrue#n不能被2到n/2的整数整除，则n是质数

在函数中，ifn=1的判断是为了排除小于等于1的数，因为小于等于1的数都不是质数。接着使用for循环从2到n//2+1（包括n//2+1），尝试用这些数去试除n。如果n能被其中任何一个数整除，那么n就不是质数，返回False。如果上述循环结束后，都没有找到能整除n的数，那么n就是质数，返回True。

试除法的优化是只需要判断到该数的平方根就可以了，因为如果一个数有大于它平方根的因子，那么必定有小于它平方根的因子。用Python实现如下：

importmath

defis_prime(n):

ifn=1:

returnFalse

foriinrange(2,int(math.sqrt(n))+1):

ifn%i==0:

returnFalse

returnTrue

埃氏筛法是一种常见的筛法，可以用来求出一定范围内的所有质数。具体实现是从2开始，将所有小于等于n的数标记为质数，然后从2开始枚举，将所有该数的倍数标记为合数，最后剩下的就是质数。用Python实现如下：

defget_primes(n):

is_prime=[True]*(n+1)

primes=[]

foriinrange(2,n+1):

ifis_prime[i]:

primes.append(i)

forjinrange(i*i,n+1,i):

is_prime[j]=False

returnprimes

上述代码中，is_prime列表记录每个数是否为质数，初始化为True，primes列表记录找到的质数。枚举到i时，如果i是质数，则将其加入primes中，并将i的倍数都标记为合数。

转载请注明：http://www.aierlanlan.com/rzdk/6383.html