[数据结构与算法]LeetCode#204. 计数质数

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

?

示例 1：

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

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

输入：n = 1
输出：0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-primes
?

这道题我们采用埃拉托色尼筛选法_百度百科

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <3:
            return 0
        else:
            dp=[1]*n #创建数组（先默认全是质数）
            dp[0],dp[1]=0,0 #0和1不是质数
            for i in range(2,n):
                for i in range(i*i,n,i): #进行优化，从i*i开始即可，减少重复
                    dp[i]=0
            return sum(dp) #质数全部对应为1