筛素数

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 using namespace std;
 5 const int maxn = 10000000;
 6 const int maxp = 700000;
 7 const int MOD = 1e9;
 8 typedef long long LL;
 9 int vis[maxn]; //vis[i] = 1是合数、vis[i] = 0是素数或者1
10 int prime[maxp];
11 // 筛素数
12 void sieve(int n){
13     int m = (int)sqrt(n + 0.5); // 避免浮点误差
14     memset(vis,0,sizeof vis);
15     for(int i = 2 ; i <= m ; i++) if(!vis[i])
16         for(int j = i * i ; j <= n ; j += i) vis[j] = 1;
17 }
18 // 生成素数表，放在prime数组中，返回素数的个数
19 int gen_primes(int n){
20     sieve(n);
21     int c = 0;
22     for(int i = 2 ; i <= n ; i++)if(!vis[i])
23         prime[c++] = i;
24     return c;
25 }
26 int main(){
27     int c = gen_primes(100);
28     for(int i = 0 ; i < c ; i++)
29         printf("%d
",prime[i]);
30     return 0;
31 }