本文最后更新于298 天前,其中的信息可能已经过时,如有错误请发送邮件到big_fw@foxmail.com
#include<iostream>
using namespace std;
bool isvis[20000];
int p[20000];
int c;
void get_prime(int n) //O(nlog(logn))
{
for(int i =2;i<=n;i++)
{
if(isvis[i] == false)
{
p[c++] = i;
for(int j = i*2;j<=n;j+=i)
isvis[j] = true;
}
}
}
void GetPrime(int n){ //O(n)
for(int i =2;i<=n;i++)
{
if(isvis[i] == false) p[c++] = i;
for(int j = 0; p[j]*i <= n && j<=c;j++)
{
isvis[p[j]*i] = true;
if(i%p[j]==0) break;
}
}
}
int main(){
int n;
cin>>n;
//get_prime(n);
GetPrime(n);
for(int i =0 ;i<c;i++)
cout<<p[i]<<' ';
return 0;
}