204. 計數(shù)質(zhì)數(shù)

題目

首先從 2 開始，我們知道 2 是一個素數(shù)，那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8... 都不可能是素數(shù)了。

然后我們發(fā)現(xiàn) 3 也是素數(shù)，那么 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12... 也都不可能是素數(shù)了。

我們維護一個list：isprime。初始把isprime全部置為True，然后遍歷這個list。如果為true，，表示這個數(shù)為質(zhì)數(shù)，則ans加1，然后把當(dāng)前數(shù)字的倍數(shù)對應(yīng)的isprime置為False。如果為False，表明當(dāng)前這個數(shù)為合數(shù)，不做任何操作。

class Solution:
    def countPrimes(self, n: int) -> int:
        isprime = [True] * (n-1)
        ans = 0
        for i in range(1,n-1):
            if isprime[i]:
                ans += 1
                p = i + i + 1
                while p<n-1:
                    isprime[p] = False
                    p += i + 1
        return ans