力扣LeetCode 204. 计数质数
程序员文章站
2022-03-06 08:21:59
...
用一个vector记录出现过所有质数,因为一个数字可以被分为很多个质数相乘,所以记录一个数字是不是质数,只要看它能不能被其它质数整除,所以只要用1——n的数字去除以 vector中的质数,只要能被其中一个质数整除就说明不是质数,转到下一个数字,如果除以所有vector中质数后都不能被除尽,说明为质数,将其放入vector中。
class Solution {
public:
int countPrimes(int n) {
if(n<=2){//排除特殊情况
return 0;
}
vector<int>arr;//记录所有的质数
arr.push_back(2);//当n大于等于3的时候必定有一个质数为2
for(int i=3;i<n;i++){
bool sig=true;//设置flag,如果变为false说明该数字不为质数
for(int j=0;arr[j]<=sqrt(i);j++){
if(i%arr[j]==0){
sig=false;
break;
}
}
if(sig){
arr.push_back(i);
}
}
return arr.size();
}
};
推荐阅读
-
【LeetCode】204. 计数质数
-
力扣【LeetCode】—— 旋转数组、链表反转【java】
-
力扣(leetcode)1431. Kids With the Greatest Number of Candies
-
LeetCode力扣有效的完全平方数
-
【leetcode 简单】 第五十八题 计数质数
-
LeetCode 204. 计数质数 263. 丑数 264. 丑数 II
-
力扣 (LeetCode)python刷题笔记8. 字符串转换整数 (atoi)
-
LeetCode 力扣 125. 验证回文串 isPalindrome
-
LeetCode 力扣 125. 验证回文串
-
#力扣LeetCode1351. 统计有序矩阵中的负数 @FDDLC