枚举——统计所有小于非负整数 n 的质数的数量

本文主要是介绍枚举——统计所有小于非负整数 n 的质数的数量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、问题

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

示例：
在这里插入图片描述
提示： 0 <= n <= 5 * 106

二、解题思路

很直观的思路是枚举每个数判断其是不是质数。

考虑质数的定义：在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数。

因此对于每个数 $x$ ，我们可以从小到大枚举 $[2, x - 1]$ 中的每个数 $y$ ，判断是否为 $x$ 的因数。但是这样判断一个数是否为质数的时间复杂度最差情况下会到 $O (n)$ ，时间复杂度高。

考虑到如果 $y$ 是 $x$ 的因数，那么 $\frac{x}{y}$ 也必然是 $x$ 的因数，因此我们只要校验 $y$ 或者 $\frac{x}{y}$ 即可。而如果我们每次选择校验两者中的较小数，则不难发现较小数一定落在 $\sqrt{x}]$ 的区间中，因此我们只需要枚举 $\sqrt{x}]$ 中的所有数即可，这样单次检查的时间复杂度从 $O (n)$ 降低至了 $O(\sqrt{n})$ 。

三、代码

bool isPrime(int x) {for (int i = 2; i * i <= x; ++i) {if (x % i == 0) {return false;}}return true;
}int countPrimes(int n) {int ans = 0;for (int i = 2; i < n; ++i) {ans += isPrime(i);}return ans;
}