以空间换时间:把2到n中所有的数都列出来,然后从2开始,先划掉n内所有2的倍数,然后每次从下一个剩下的数(必然是素数)开始,划掉其n内的所有倍数。最后剩下的数,就都是素数。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define MAX_NUM 10000 4 char isPrime[MAX_NUM+10];///因为数组元素只有0和1,定义为char类型比int类型节省空间 5 int main() 6 { 7 for(int i=2;i<=MAX_NUM;++i) 8 isPrime[i]=1; 9 for(int i=2;i<=MAX_NUM;++i) 10 { 11 if(isPrime[i]) 12 { 13 for(int j=2*i;j<=MAX_NUM;j++) 14 isPrime[j]=0; 15 } 16 } 17 for(int i=2;i<=MAX_NUM;++i) 18 { 19 if(isPrime[i]) 20 cout<<i<<endl; 21 } 22 return 0; 23 }