子寒的博客
0%

leetcode204 Count Primes 解题报告

发表于 更新于 分类于

英文原题

Count the number of prime numbers less than a non-negative number, n.

Example

1
2
3
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

分析

    暴力法是会超时的，这题用了一个挺巧妙的方法叫埃氏筛法，就是先假设所有数都是质数，然后从2开始每碰到一个质数就可以确定这个数的所有倍数都不是质数。可以参考这里

python 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countPrimes(self, n: int) -> int:
        if n == 0 or n == 1:
            return 0
        
        count = [True] * n
        count[0] = False
        count[1] = False
        
        for i in range(int(sqrt(n))+1):
            if count[i]:
                for j in range(i+i, n, i):
                    count[j] = False
                    
        return sum(count)

时间复杂度O(n)?