判断素数/质数的快速算法
发布时间
阅读量：
阅读量
质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个因数的数）。——via维基百科
朴素算法：
def isprime(n):
"""
:type n:int
:rtype:bool
"""
if n==1:
return False
for i in range(2,n):
if n%i==0:
return False
return True import math
def isPrime(n):
"""
:type n:int
:rtype:bool
"""
if n == 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True埃氏筛法: 运算速度更快的判断素数算法 。
可以知道除了2（2是素数）以外的其他偶数都不是素数，除了3（3是素数）以外其他能被3整除的数都不是素数。所以一个素数的整数倍都不是素数，可以利用这一点编写算法如下：
def isprime(n):
"""
:type n:int
:rtype:List[int]
"""
s=[True for i in range(n+1)]#首先默认所有的数都是质数
z=[]#存放质数
for i in range(2,n+1):#1不是质数
if s[i]:#判断是否为质数，如果没有被标记就是质数
z.append(i)
for j in range(i+i,n+1,i):#剔除倍数（如果是质数，质数的倍数一定不是质数）
s[j]=False
return z算法参考：<>
全部评论 (0)
还没有任何评论哟~