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

image-20201203195128240

思路

• 枚舉

  一般咱們用來(lái)判斷一個(gè)數(shù)比如說(shuō)23是否是質(zhì)數(shù)，我們可以用23除以[2, 23)里面的數(shù)字，一旦有數(shù)字大于1，該數(shù)字肯定就不是質(zhì)數(shù)。

  但是每次除以那么多數(shù)字，其實(shí)可以簡(jiǎn)化。

  想想一下，判斷x是否是y的因數(shù)（也就是x是否能被y整除）

  如果x是y的因素，那么y ÷ x肯定也是y的因數(shù)，所以其實(shí)只要計(jì)算[2, min(y/x, y)]是否能被y整除就行。

  那么什么時(shí)候y/x最小呢

引用一下題解，感覺(jué)比我解釋的好:

image-20201203201748756

但是此方法會(huì)超時(shí)

// 超時(shí)警告
func isPrime(x int) bool {
    for i := 2; i*i <= x; i++ {
        if x%i == 0 {
            return false
        }
    }
    return true
}

func countPrimes(n int) (cnt int) {
    for i := 2; i < n; i++ {
        if isPrime(i) {
            cnt++
        }
    }
    return
}

• 埃氏篩

  簡(jiǎn)單的說(shuō)就是，如果x是質(zhì)數(shù)，那么2x 3x 4x....這些一定不是質(zhì)數(shù)

  那么從2開(kāi)始我們就可以找出2的2倍，3倍，排除這些非質(zhì)數(shù)，一直遍歷，看數(shù)組里還有哪些質(zhì)數(shù)，數(shù)量+1，返回總數(shù)即可

  所以可以寫出如下代碼:

func countPrimes(n int) (cnt int) {
    // 創(chuàng)建一個(gè)bool數(shù)組，里面存放第N個(gè)數(shù)是否是質(zhì)數(shù)
    // 初始化，使得每個(gè)數(shù)都是質(zhì)數(shù)
    isPrime := make([]bool, n)
    for i := range isPrime {
        isPrime[i] = true
    }
    // 從2開(kāi)始 2是質(zhì)數(shù)，把數(shù)組里2的倍數(shù)都刷為素?cái)?shù)
    for i := 2; i < n; i++ {
        if isPrime[i] {
            cnt++
            for j := 2 * i; j < n; j += i {
                isPrime[j] = false
            }
        }
    }
    return
}

image-20201203204422642

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

image-20201203204605411