LeetCode 204. 计数质数 Python3

题目

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

示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：
输入：n = 0
输出：0

示例 3：
输入：n = 1
输出：0

提示：
0 <= n <= 5000000

个人思路+个人题解（超时）

双循环 一层循环判断，一层循环遍历

为了优化 用了for else 和开方两种方法

from math import sqrt
def isPrime ( a):
        flag = False
        for i in range(2,int(sqrt(a))+1):
            if(a%i==0):
                break
        else:
            flag = True
        return flag

class Solution:    
    def countPrimes(self, n: int) -> int:
        res = 0
        for i in range(2,n):
            if(isPrime (i)):
                res+=1
        return res

在1500000 的时候超时了

优秀思路+题解

其他大佬的题解

效率提升的关键在于埃拉托斯特尼筛法，简称埃式筛，也叫厄拉多塞筛法：

要得到自然数n以内的全部质数，必须把不大于根号 n 的所有质数的倍数剔除，剩下的就是质数。

肯定有同学想问了，为什么埃式筛只需要剔除根号n以内的质数倍数？为什么不是每个数的倍数都进行剔除？我们知道偶数的倍数肯定是偶数，可以剔除，那为什么不是剔除根号n以内的所有奇数的倍数呢？

这个时候我们需要了解一个定理，叫算术基本定理：

任何一个合数(非质数)，都可以以唯一的形式被写成有限个质数的乘积，即分解质因数。

这个定理使用反证法很好证明，在理解了算数基本定理后，我们就知道所有超过根号 n 的合数都可以进行因式分解，其中最小的因子必然为根号 n 以内的一个质数，这样我们只要剔除掉根号 n 以内的质数倍数，就可以排除掉 n 以内的所有合数了，之后剩下来的数就都是质数啦。

代码：

def count_primes_py(n):
    """
    求n以内的所有质数个数（纯python代码）
    """
    # 最小的质数是 2
    if n < 2:
        return 0

    isPrime = [1] * n
    isPrime[0] = isPrime[1] = 0   # 0和1不是质数，先排除掉

    # 埃式筛，把不大于根号 n 的所有质数的倍数剔除
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            isPrime[i * i:n:i] = [0] * ((n - 1 - i * i) // i + 1)

    return sum(isPrime)

作者：bruce-33
链接：https://leetcode-cn.com/problems/count-primes/solution/pythonzui-you-jie-fa-mei-you-zhi-yi-liao-ba-by-bru/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。