C\C++ 埃氏筛法

 1 埃氏筛法的基本思想 ：从2开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的。

 1 #include <iostream>
 2 using namespace std;
 3 const int maxn = 1000;
 4 int visit[maxn];  
 5 void Prime(int n)
 6 {          
 7     visit[0] = visit[1] = 1;  //0,1不是素数
 8     for (int i = 2; i <= n; i++) {
 9         if (!visit[i]) {         //如果i是素数，i的倍数都不是素数
10             for (int j = i*i; j <= n; j += i) 
11             { 
12                 visit[j] = 1;
13             }
14         }
15     }
16 }
17 int main()
18 {
19     int n;
20     cin>>n;
21     Prime(n);
22     for(int i = 1; i <= n; i++ )
23     {
24         if(!visit[i])
25         cout<<i<<endl;
26     }
27     return 0;
28 }