A24190. 素数个数
填空题
中等
知识点
题目描述
素数个数
题目描述
编程求2∼n(n为大于2的正整数)中有多少个素数。
输入
输入n(2≤n≤50000)。
输出
素数个数。
输入样例
10
输出样例
4
参考答案
#include<bits/stdc++.h>
using namespace std;
//判断一个大于等于2的数是否是质数
bool isPrime(int n)
{
for(int i = 2; i <= sqrt(n); ++i)
if(n % i == 0)
return false;
return true;
}
int main()
{
int n, s = 0;//s:质数个数
cin >> n;
for(int i = 2; i <= n; ++i)
{
if(isPrime(i))
s++;
}
cout << s;
return 0;
}答案解析
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, s = 0;//s:质数个数
bool isPrime[50005] = {};
cin >> n;
for(int i = 1; i <= n; ++i)
isPrime[i] = true;
isPrime[0] = isPrime[1] = false;
for(int i = 2; i <= n; ++i)
{
if(isPrime[i])
{
for(int j = i*2; j <= n; j += i)
isPrime[j] = false;
}
}
for(int i = 2; i <= n; ++i)
{
if(isPrime[i])
s++;
}
cout << s;
return 0;
}
上一题
下一题