素数筛再优化
#include <iostream>
#include <memory.h>
#include <cmath>
using namespace std;
int main()
{
long long int n;
cin>>n;
long long int a[n+1];
memset(a,0,sizeof(a)+1);
long long int m = sqrt(n);
for(long long int i = 2; i <= m; i++)
{
if(!a[i])
{
for(long long j = i + i; j <= n; j+=i)
a[j] = 1;
}
}
for(long long int i = 2; i <= n; i++)
if(!a[i])
cout<<i<<"\t";
return 0;
}
优化依据: