LeetCode 204. Count Primes--从一开始的质数个数--C++,Python解法

LeetCode 204. Count Primes–从一开始的质数个数–C++,Python解法

---

LeetCode题解专栏：LeetCode题解
我做的所有的LeetCode的题目都放在这个专栏里，大部分题目Java和Python的解法都有。

---

题目地址：Count Primes - LeetCode

---

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.

---

这道题目是算有多少个质数在一个范围内，做法不难。
Python解法如下：

class Solution:
    def countPrimes(self, n: int) -> int:
        def judge(i, l):
            nonlocal count
            flag = 0
            for j in l:
                if j*j > i:
                    break
                if i % j == 0:
                    return
            if flag == 0:
                    l.append(i)
                    count += 1

        l = [2, 3]
        count = 2
        if n == 1:
            return 0
        elif n == 2 or n == 3:
            return n-1
        for i in range(4, n):
            judge(i, l)
        return count

这个解法超时了。。。
正确的解法如下：

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

C++解法如下：

class Solution {
public:
    int countPrimes(int n) {
        if (n<=2) return 0;
        vector<bool> prime(n, true);
        prime[0] = false, prime[1] = false;
        for (int i = 0; i < sqrt(n); ++i) {
            if (prime[i]) {
                for (int j = i*i; j < n; j += i) {
                    prime[j] = false;
                }    
            }    
        }
        return count(prime.begin(), prime.end(), true);
    }
};