本文主要是介绍LeetCode--204 计数质数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
统计所有小于非负整数 n 的质数的数量。
示例
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
class Solution {
public:int countPrimes(int n) {if (n <= 2) return 0;int cnt = 0;vector<bool> isPrime(n, true);//循环最大值一定是小于n的开方/*i=2j=4;p[4]=f;j=6;p[6]=f;j=9;p[8]=f;j=10;i=3;j=9;p[9]=f;*/for (int i = 2;i*i<n;i++) {/*如果一个数是质数，那么它的任意倍数(j+=i)都是合数如说求9以内的质数个数,那么只要划掉sqrt(9)以内的质数倍数,剩下的即全为质数. 所以在划去倍数 的时候也是从i*i开始划掉,而不是i+i.j的初值：因为(i-x)*i，x为任意大于0的正整数，在上一轮中一定已经被判断过了，所以从(i-1)*i+i=i*i开始判断*/if (isPrime[i] == true) {for (int j = i*i;j<n;j += i) {isPrime[j] = false;}}}for (size_t i = 2; i < n; i++){if (isPrime[i]){cnt++;}}return cnt;}
};
这篇关于LeetCode--204 计数质数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
