大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定整数n，返回所有小于整数n的质数的数量。”
2、题目描述
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1： 输入： n = 10 输出： 4 解释： 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2： 输入： n = 0 输出： 0
二、解题
1、思路分析
题意要求出所有小于整数n的质数的数量。
统计质数数量有很多方法，直观的思路是枚举每个数判断是不是质数。
首先来看一下质数的性质：
- 在大于的1的自然数中，除了1和它本身以外不再有其他因数的自然数。
根据质数的性质，对于每个数x，可以枚举[2,x-1]中的每个数y，判断y是否为x的因数，但是这样时间复杂度过高，需要考虑其他方法。
考虑到如果y是x的因数，那么xy\frac{x}{y}yx必然也是x的因数，因此只要校验y或者xy\frac{x}{y}yx即可。
进一步思考，只需要校验y和xy\frac{x}{y}yx之间的较小值，较小值会落在 [2,x\sqrt{x}x] 的区间中，因此只需要枚举 [2,x\sqrt{x}x] 区间中中的所有数即可。
2、代码实现
代码参考：
class Solution { public int countPrimes(int n) { int ans = 0; for (int i = 2; i < n; ++i) { ans += isPrime(i) ? 1 : 0; } return ans; } public boolean isPrime(int x) { for (int i = 2; i * i <= x; ++i) { if (x % i == 0) { return false; } } return true; } }
3、时间复杂度
时间复杂度：O(nx\sqrt{x}x)
单个数检查的时间复杂度为O(x\sqrt{x}x)，一共要检查O(n)个数，因此总时间复杂度为O(nx\sqrt{x}x)。
空间复杂度：O(1)
只需要常数级的变量空间。
三、总结
枚举每个数字是否为质数。
判断素数的方法参考定义，对于某个数字 n，i 从 2 开始枚举判断是否满足 n % i == 0 ，如果找到了 n 的因子，就返回 false。
注意 i 遍历到最大 n\sqrt{n}n 即可。
因为 n 如果不是质数，那么至少有一个因子是小于等于 n\sqrt{n}n 的。
如果某个因子 x >= n\sqrt{n}n ，那么 nx\frac{n}{x}xn <= x，而 nx\frac{n}{x}xn 也是 n 的因子）。
