计算质数
题目描述：
给定一个非负整数n，计算所有小于n的质数的数量。
感谢：
特别感谢@mithmatt添加此问题并创建所有测试用例。
方法解析：
每当找到一个质数时，将其所有整数倍的数字标记为非质数。
如下面的示意图所示：
注意事项：
1. 当发现质数i时，应从i*i开始排除其整数倍的数，而非从i+i开始，因为小于i*i的数已经被之前的小于i的质数排除过了。
2. 在计算i*i时应注意数据类型的转换，以防止数值溢出。
代码实现：
class Solution {
public:int countPrimes(int n) {int count = 0;if(n <= 2)return count; // 如果n小于等于2，则没有质数
vector
for(int i = 2; i
count++; // 计数器加1
// 排除i的所有整数倍
for(long long j = (long long)i * i; j
}
}
return count;
}
示例图解：
京公网安备 11010802041100号