Leetcode 204. 计数质数
题目描述
统计所有小于非负整数 n 的质数的数量。
示例 1:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
计算小于非负整数 n 的质数数量有两种方式，一种是统计小于 n 的所有的质数，另一种是排除小于 n 的所有非质数，统计剩下的数。
普通解法
除了 2,3 以外，所有的质数都分布在 6*x 的两侧，例如 5,7,11,13...，其中 x 为正整数。
证明如下：
对于数列：
6x-1,6x,6x+1,6x+2,6x+3,6x+4,6(x+1)-1,6(x+1),6(x+1)+1...
观察
6x+1
与
6(x+1)-1
之间的数列:
6x+2,6x+3,6x+4
即
2(3x+1),3(2x+1),2(3x+2)
可发现都有非 1 和自身之外的约数，因此都是非质数。
因此判断一个数是否为质数，可以首先过滤不在 6x 两侧的数，其次，如果一个数为非质数，则必然可以由质数相乘获得，因此若 n 不被不大于
q(q\le\sqrt n)
的所有质数整除，则 n 为质数。
import math
class Solution:
def countPrimes(self, n: int) -> int:
if n<3:
return 0
if n==3:
return 1
if n<6:
return 2
cnt,idx=2,5
while idx<n:
if self.isPrime(idx):
cnt+=1
if idx+2<n and self.isPrime(idx+2):
cnt+=1
idx+=6
return cnt
def isPrime(self,idx):
if idx%2==0 or idx%3==0:
return False
i,end=5,int(math.sqrt(idx))
while i<=end:
if idx%i==0 or idx%(i+2)==0:
return False
i+=6
return True 代码前几行判断 n 是否包含质数 2,3，while 循环取 6x 两侧的数，调用 isPrime 函数判断是否为质数，cnt 用于统计总质数的个数。
这种判断一个数是否为质数的方式，比较适合用于单独判断数是否为质数，如果用于统计一个范围内的质数，则存在重复的 isPrime 判断函数调用，性能较差，可能会超时。
埃拉托斯特尼筛法
该方式通过排除给定范围内的所有非质数，统计剩下的元素个数即可。以 primes 数组标识 n 内的所有数值，下标即为对应的数值，不妨以 1 表示质数，0 表示非质数。则标识 primes 数组中下标是
i
的倍数的元素为 0 即可，其中
2\le i \le \sqrt {n-1}
。
因为排除过程是从 2 开始的，例如先排除下标为 2 的倍数的元素，然后排除下标为 3 的倍数的元素，依次进行，所以对于数值 x，排除下标为 x 的倍数的元素时，不用排除
x*2,x*3,x*4 ... x*(x-1)
等下标位置，可以直接从
x*x,x*(x+1),x*(x+2)...
开始排除即可。
import math
class Solution:
def countPrimes(self, n: int) -> int:
if n<3:
return 0
primes=[1]*n
target=int(math.sqrt(n-1))
for i in range(2,target+1):
if primes[i]:
primes[i*i:n:i]=[0]*len(primes[i*i:n:i])
return sum(primes)-2本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.05.10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读