0204. Count Primes - chasel2361/leetcode GitHub Wiki

Given an integer n, return the number of prime numbers that are strictly less than n.

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

Example 2:
Input: n = 0
Output: 0

Example 3:
Input: n = 1
Output: 0

這題要解不算太難，只要從2到n檢查是否為質數即可，一開始寫出來的程式碼如下：

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2: return 0
        
        cnt = 0
        for n_ptr in range(2, n):
            ptr_basis = round(n_ptr**0.5)
            is_prime = True
            for i in range(2, ptr_basis + 1):
                if n_ptr % i == 0:
                    is_prime = False
                    break
            if is_prime:
                cnt += 1
        return cnt

不過這樣寫的問題是算太慢，系統過不了
所以參考了大大的寫法，發現有一個特定方法叫做埃拉托斯特尼篩法(sieve of Eratosthenes)
概念是把所有的數列出來，然後取質數出來，把質數的倍數篩掉，這樣只要篩到最小質數可能發生的數(n**0.5)就可以了
寫出來的程式碼如下：

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 3: return 0
        
        primes = [1] * n
        primes[0] = primes[1] = 0
        for i in range(2, round(n**0.5) + 1):
            if primes[i]:
                primes[i*i: n: i] = [0] * ((n-1 - i*i) // i + 1)
                # n = 11
                # i = 2
                # (n-1-i*i)//i + 1
                # (n-1)               # get total # of indicies for n (non-inclusive)
                #     -i*i            # shift to get # of slots in range of interest
                #          //i        # get number of groups
                #              + 1    # get number of slots
                # strikes[2*2:11:2]  = [0] * ((11-1-2*2)//2 + 1
                # strikes[4:11:2]    = [0] * 4
                # s[4], s[6], s[8], s10] = 0, 0, 0, 0
        return sum(primes)

這樣寫的時間複雜度是O(n), 空間複雜度比較複雜，是O(nloglogn) wiki有提供演算概念圖如下 sieve of Eratosthenes

另外如果用C++寫的話會長成這樣

# include <vector>
class Solution {
public:
    int countPrimes(int n) {
        if (n < 3) return 0;
        vector<bool> seen(n, false);
        int ans = 0;
        for (int i=2; i < n; i++){
            if (seen[i]) continue;
            ans++;
            for (long mult=(long)i * i; mult < n; mult += i){
                seen[mult] = true;
            }
        }
        return ans;
    }
};

差別在於C++需要另外用一個變數來儲存質數的個數這樣

⚠️ **GitHub.com Fallback** ⚠️