Leetcode 204. 计数质数

题目描述

统计所有小于非负整数 n 的质数的数量。

示例 1:

输入: 10

输出: 4

解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

计算小于非负整数 n 的质数数量有两种方式，一种是统计小于 n 的所有的质数，另一种是排除小于 n 的所有非质数，统计剩下的数。

普通解法

除了 2,3 以外，所有的质数都分布在 6*x 的两侧，例如 5,7,11,13...，其中 x 为正整数。

证明如下：

对于数列：

观察 与 之间的数列:

即

可发现都有非 1 和自身之外的约数，因此都是非质数。

因此判断一个数是否为质数，可以首先过滤不在 6x 两侧的数，其次，如果一个数为非质数，则必然可以由质数相乘获得，因此若 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 数组中下标是 的倍数的元素为 0 即可，其中 。

因为排除过程是从 2 开始的，例如先排除下标为 2 的倍数的元素，然后排除下标为 3 的倍数的元素，依次进行，所以对于数值 x，排除下标为 x 的倍数的元素时，不用排除 等下标位置，可以直接从 开始排除即可。

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