欢迎访问LeetCode题解合集

题目描述

统计所有小于非负整数 n 的质数的数量。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

提示：

• 0 <= n <= 5 * 10^6

题解：

法一：

枚举。

依次枚举 2~n-1 ，判断每个数是否是质数。

时间复杂度：$O(n\sqrt{n})$

额外空间复杂度：$O(1)$

class Solution {
public:
    bool is_prime( int x ) {
        for ( int i = 2; i <= x / i; ++i )
            if ( x % i == 0 ) return false;
        return true;
    }
    int countPrimes(int n) {
        int cnt = 0;
        for ( int i = 2; i < n; ++i )
            cnt += is_prime( i );
        return cnt;
    }
};
/*
时间：676ms，击败：20.51%
内存：5.7MB，击败：99.50%
*/

法二：

埃氏筛。

时间复杂度：$O(nloglogn)$

额外空间复杂度：$O(n)$

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> vis( n );
        int cnt = 0;
        for ( int i = 2; i < n; ++i ) {
            if( vis[i] ) continue;
            ++cnt;
            if ( i > n / i ) continue;
            for ( int j = i * i; j < n; j += i )
                vis[j] = true;
        }
        return cnt;
    }
};
/*
时间：28ms，击败：92.30%
内存：6.2MB，击败：82.24%
*/

法三：

线性筛。

时间复杂度度：$O(n)$

额外空间复杂度：$O(n)$

class Solution {
public:
    int countPrimes(int n) {
        vector<int> primes;
        vector<bool> vis(n);
        for ( int i = 2; i < n; ++i ) {
            if( !vis[i] ) primes.emplace_back( i );
            for( int j = 0; primes[j] <= n / i; ++j ) {
                vis[i * primes[j]] = true;
                if ( i % primes[j] == 0 ) break;
            }
        }
        return primes.size();
    }
};
/*
时间：88ms，击败：62.28%
内存：9.1MB，击败：45.87%
*/

这时间有点离谱。。。