Medium

题目描述

给你一个整数 n ，返回小于 n 的质数的个数。

示例 1：

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

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

约束条件：

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

提示：

  • 检查 [1, n - 1] 范围内的所有整数效率不高。考虑一个更好的方法。
  • 由于大多数数字都不是质数，我们需要一种快速的方法来排除非质数整数。
  • 使用埃拉托斯特尼筛法。

解题思路

这是一个经典的数论问题，有多种解法：

方法一：暴力枚举（不推荐） 对每个数字从2开始检查是否为质数，时间复杂度为O(n²)，在n较大时会超时。

方法二：优化的暴力枚举 对每个数字只需检查到√n即可判断是否为质数，时间复杂度为O(n√n)，仍然较慢。

方法三：埃拉托斯特尼筛法（推荐） 这是最经典也是最高效的解法。基本思想是：

  1. 创建一个布尔数组标记每个数是否为质数，初始都设为true
  2. 从2开始，将每个质数的所有倍数标记为非质数
  3. 优化：只需要筛选到√n，因为大于√n的质数的最小倍数已经被较小的质数筛掉了
  4. 再次优化：从i²开始筛选，因为i×2, i×3, …, i×(i-1)都已经被更小的质数筛掉了

这个算法的时间复杂度接近O(n log log n)，空间复杂度O(n)，是解决这类问题的标准方法。

代码实现

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

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

public class Solution {
    public int CountPrimes(int n) {
        if (n <= 2) return 0;
        
        bool[] isPrime = new bool[n];
        Array.Fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) count++;
        }
        
        return count;
    }
}

var countPrimes = function(n) {
    if (n <= 2) return 0;

    const isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;

    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    let count = 0;
    for (let i = 2; i < n; i++) {
        if (isPrime[i]) count++;
    }

    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n log log n)
空间复杂度O(n)

相关题目