记录编号	576665	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[模板]求素数	最终得分	100
用户昵称	qyd	是否通过	通过
代码语言	C++	运行时间	8.653 s
提交时间	2022-10-14 22:08:14	内存使用	201.71 MiB

#include<iostream>
using namespace std;
int p[46000001]={};  //对1~n编号，0代表是素数，1代表合数； 
int prime[23000001]; int num=0;  //用于表示第num个素数；
int main()
{
	freopen("sssxmoban.in","r",stdin);
	freopen("sssxmoban.out","w",stdout);
	
	int N;
	cin>>N;
	cout<<N<<endl;

	for(int i=2;i<=N;i++)  //线性筛；
	{
		if(p[i]==0)   
		{
			num++;
			prime[num]=i;
		}	     
		  
	    for(int j=1;j<=num&&i*prime[j]<=N;j++)  //从第一个素数开始尝试； 
	    {
	    	p[i*prime[j]]=1;
	    	
	    	if(i%prime[j]==0)
	    	  break;    	
		}
    }
    
	for(int i=1;i<=num;i++)
	  cout<<prime[i]<<" ";     
	
    return 0;
}