本题要求使用筛法求出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

AC

vector<int> sieve(int n)
{
	vector<int> a;//准备储存质数的容器
	int i,j;
	vector<bool> flag(n+1,true);//用于记录质数，相当于筛漏
	for(i=2;i*i<=n;i++)//任何数都可以拆成一个大数乘一个小数，极限情况是平方
	{
		if(flag[i])//筛法精髓，不重复删去
		{
			for(j=i*2;j<=n;j+=i)//倍数都筛去
			{
				flag[j]=0;
			}
		}
	}
	for(i=2;i<=n;i++)
	{
		if(flag[i])
		a.push_back(i);
	}
	return a;
}