本题要求使用筛法求出1~N以内的质数。
函数接口定义：
vector<int> sieve(int n); //函数声明, 求n以内的质数
求n以内的质数。其中 n是传入的参数。n 的值不超过10 000 000的范围； 求出的质数存入容器vector并返回。
裁判测试程序样例：
#include <iostream>#include <vector>using namespace std;vector<int> sieve(int n); //函数声明,求n以内的质数int main(int argc, char const *argv[]){ int n; cin >> n; vector<int> ans = sieve(n); cout << ans.size() << endl; for (int i = 0; i < ans.size(); i++) { cout << ans[i]; if (i < ans.size() - 1)cout << " ";
} cout << endl; return 0;
}/* 请在这里填写答案 */
输入样例：
输入在一行中给出一个正整数N，其值不超过10 000 000。
10
输出样例：
输出首先在一行中输出指定范围内的质数个数，然后在另一行输出指定范围内的所有质数，以空格分隔，但是最后一个质数后面没有多余空格。
4
2 3 5 7
作者李廷元单位民用航空飞行学院代码长度限制16 KB时间限制400 ms内存限制64 MBvector<int> sieve(int n){
vector<int>a;
int i,j,*flag=new int[n+1];
for(i=2; i<=n; i++)
flag[i]=1;
for(i=2; i*i<=n; i++)
{
if(flag[i])
{
for(j=i+i; j<=n; j+=i)
flag[j]=0;
}
}
for(i=2;i<=n;i++)
if(flag[i]) a.push_back(i);
return a;
}
本题要求使用筛法求出1~N以内的质数。
函数接口定义：
vector<int> sieve(int n); //函数声明, 求n以内的质数
求n以内的质数。其中 n是传入的参数。n 的值不超过10 000 000的范围； 求出的质数存入容器vector并返回。
裁判测试程序样例：
#include <iostream>#include <vector>using namespace std;vector<int> sieve(int n); //函数声明,求n以内的质数int main(int argc, char const *argv[]){ int n; cin >> n; vector<int> ans = sieve(n); cout << ans.size() << endl; for (int i = 0; i < ans.size(); i++) { cout << ans[i]; if (i < ans.size() - 1)cout << " ";
} cout << endl; return 0;
}/* 请在这里填写答案 */
输入样例：
输入在一行中给出一个正整数N，其值不超过10 000 000。
10
输出样例：
输出首先在一行中输出指定范围内的质数个数，然后在另一行输出指定范围内的所有质数，以空格分隔，但是最后一个质数后面没有多余空格。
4
2 3 5 7
作者
李廷元
单位
民用航空飞行学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
vector<int> sieve(int n){
vector<int>a;
int i,j,*flag=new int[n+1];
for(i=2; i<=n; i++)
flag[i]=1;
for(i=2; i*i<=n; i++)
{
if(flag[i])
{
for(j=i+i; j<=n; j+=i)
flag[j]=0;
}
}
for(i=2;i<=n;i++)
if(flag[i]) a.push_back(i);
return a;
}