筛素数判定素数

判定1-2^31以内的数是否是素数，比一个一个判定要高很多。

普通筛法：

 1 #include <iostream> 
 2 #include <cstdio> 
 3 #include <algorithm>  
 4 #include <cmath>  
 5 #include <cstring>  
 6 #include <map>  
 7 using namespace std;
 8 
 9 const int maxn = 1e6;
10 int vis[maxn + 1] = { 1,1 };
11 int prime[maxn + 1];
12 int cnt = 0;
13 
14 void create_prime()
15 {
16     int i, j;
17     int m = sqrt(maxn + 0.5);
18     for (i = 2; i <= m; i++)
19         if (!vis[i]) {
20             for (j = i*i; j <= maxn; j += i)
21                 vis[j] = 1;
22         }
23     for (i = 2; i <= maxn; i++)
24         if (!vis[i]) prime[cnt++] = i;
25 }
26 
27 int judge(int n)
28 {
29     if (n == 0 || n == 1) return 0;
30     for (int i = 0; prime[i] * prime[i] <=n&&i<cnt; i++) {
31         if (n%prime[i] == 0) return 0;
32     }
33     return 1;
34 }
35 
36 int main()
37 {
38     int n;
39     create_prime();
40     while (scanf("%d",&n)==1)
41     {
42         if (n == -1) break;
43         printf("%d
", judge(n));
44     }
45     return 0;
46 }

更高效的筛：

 1 #include <cstdio>  
 2 #include <iostream>  
 3 #include <cmath>  
 4 using namespace std;
 5 
 6 #define N 50001  
 7 
 8 bool isprime[N];
 9 int prime[N], nprime;
10 
11 void doprime()
12 {
13     long long  i, j;
14     nprime = 0;
15     for (i = 0; i<N; i++)
16         isprime[i] = true;
17     isprime[1] = 0;
18     for (i = 2; i<N; i++)
19     {
20         if (isprime[i])
21         {
22             prime[++nprime] = i;
23             for (j = i*i; j<N; j += i)
24                 isprime[j] = false;
25         }
26     }
27 }
28 
29 int isp(int n)
30 {
31     if (n == 0 || n == 1) return 0;
32     int i, k = (int)sqrt(double(n));
33     for (i = 1; prime[i] <= k; i++)
34         if (n%prime[i] == 0)
35             return 0;
36     return 1;
37 }
38 
39 int main()
40 {
41     freopen("E:\1.txt", "w", stdout);
42     doprime();
43     int n;
44     while (scanf("%d",&n)==1)
45     {
46         if (n == -1) break;
47         printf("%d
", isp(n));
48     }
49     return 0;
50 }

优化的

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 using namespace std;
 6 const int maxn = 65537;
 7 int vis[maxn + 1] = { 1,1 };
 8 int prime[maxn + 1];
 9 int cnt = 0;
10 
11 void eratosthenes()
12 {
13     int i, j;
14     int m = sqrt(maxn + 0.5);
15     for (i = 2; i <= m; i++) {
16         if (!vis[i]) {
17             for (j = i*i; j <= maxn; j+=i) vis[j] = 1;
18         }
19     }
20     for (i = 2; i <= maxn; i++)
21         if (!vis[i]) prime[cnt++] = i;
22 }
23 
24 int isp(int n)
25 {
26     if (n == 0 || n == 1) return 0;
27     int k = sqrt(n + 0.5);
28     for (int i = 0; prime[i]<=k; i++)
29         if (n%prime[i] == 0) return 0;
30     return 1;
31 }
32 
33 int main()
34 {
35     int n;
36     eratosthenes();
37     while (scanf("%d",&n)==1) {
38         if (n == -1) break;
39         printf("%d
", isp(n));
40     }
41     return 0;
42 }