埃筛在ACM中不可用
其实就是筛素数，我找到完整的名字了！
要得到自然数n以内的全部素数，必须把不大于 
的所有素数的倍数剔除，剩下的就是素数
我找的例题比较神奇，它限制了空间1MB，这样的话假如我要找出第n个素数是什么，我筛的范围就要比n要大很多
但是到底大多少呢？不清楚，但是这个题空间限定了，只能一个一个判断，我这里强行线性筛了
根据数据得到了最大筛到多少
其实如果空间够的话，尽可能多筛一些也是可以的，这里就涉及一个时空权衡的问题
1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 const int maxn=373682; 5 bool v[maxn]; 6 int n; 7 void sieve(int x) 8 { 9 int m=int(sqrt(x)+0.5); 10 for(int i=2;i<=m;i++) 11 if(!v[i]) 12 for(int j=i*i;j<=x;j+=i) 13 v[j]=1; 14 } 15 int main() 16 { 17 scanf("%d",&n); 18 sieve(maxn); 19 int cnt=0; 20 for(int i=2;i<n;i++) 21 { 22 if(!v[i]) 23 printf("%d ",i); 24 } 25 return 0; 26 }