小于N的素数个数
程序员文章站
2024-03-14 21:12:59
...
class Solution {
public:
/**
* 计算小于N的素数的个数。
* @param n int整型
* @return int整型
*/
int countPrimes(int n) {
// write code here
vector<int> vec;
vec.push_back(2);
vec.push_back(3);
vec.push_back(5);
vec.push_back(7);
vec.push_back(11);
if(n == 0 || n == 1){
return 0;
} else if(n <= 11) {
int i = 0;
for(int j = 0 ; j < vec.size(); j++) {
if(vec[j] < n) {
i++;
} else {
break;
}
}
return i;
}
bool flag = true;
for(int k = 12; k < n ; k++) {
flag = true;
for (int i = 0; i < vec.size(); i++) {
if( vec[i] * vec[i] > k ) {
break;
}
if(k % vec[i] == 0 ) {
flag = false;
break;
}
}
if(flag) {
vec.push_back(k);
}
}
return vec.size();
}
};
上一篇: 筛选法求质数
下一篇: 求n以内素数个数问题详解