0204. Count Primes.md

题目

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

Example:

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

我的思路

此题要求统计n以内的素数个数。首先我想到遍历n，每个数都判断其是否能被[2,$\sqrt{n}$]中的数整除，但这种方式的时间复杂度为O(n²)，肯定会超时。题目中给了提示链接，使用埃拉托斯特尼筛法(Sieve of Eeatosthese)。其原理是从2开始，直到$\sqrt{n}$，将每个素数的倍数都标记为合数。最后没被标记的数就是素数。因此需要建一个长度为n-1的数组来记录每个数是否为合数。

class Solution:
    def countPrimes(self, n: int) -> int:
        res = 0
        prime = [True] * (n-1)
        for i in range(2,int(n**0.5)+1):
            if prime[i-1]:
                j = 2
                while j*i < n:
                    prime[(j*i)-1] = False
                    j += 1
                    
        for x in range(1,n-1):
            if prime[x]:
                res += 1
                
        return res