###### tags: `Leetcode` `medium` `math` `python` `c++`

# 204. Count Primes

## [題目連結:] https://leetcode.com/problems/count-primes/description/

## 題目:
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

## 解題想法:
* 題目為求小於n的所有質數(質數不含0,1)
* 想法:
* 可參考說明[https://www.796t.com/content/1547766215.html]
* primes=[True] * n
* curNum: 為判斷當前的數
* mul: 為curNum該數的倍數
* 終止條件為while (curNum * curNum < n)
* curNum從2開始遍歷，若為True
* 將其倍數全改為False
* curNum+=1

## Python:

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        #time: O(NlogN)
        if n<3:
            return 0
        primes=[True]*n
        primes[0]=False
        primes[1]=False
        curNum=2 #當前判斷的數
        while (curNum*curNum<n):
            mul=curNum #mul為倍數
            #若該數為prime
            if primes[curNum]:
                #則其倍數全改為false
                mul+=curNum
                while mul<n:
                    primes[mul]=False
                    mul+=curNum
            curNum+=1
        return sum(primes)
    
    
result = Solution()
ans = result.countPrimes(10)
print(ans)

## C++:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int countPrimes(int n) {
        int res=0;
        vector<bool> primes(n,true);
        for (int i=2; i<n; i++){
            if (!primes[i]) //not prime
                continue;
            res+=1;
            //let mul of prime to fasle
            for (int j=2; i*j<n; j++){
                primes[i*j]=false;
            }
        }
        return res;
    }
};

int main(){
    Solution res;
    int ans=res.countPrimes(10);
    cout<<ans<<endl;
    return 0;
}