POJ 2262 Goldbach's Conjecture（Eratosthenes筛法）

题意：

哥德巴赫猜想，把一个数用两个奇素数表示出来。

思路：
先用Eratosthenes筛法打个素数表，之后枚举即可。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 const int maxn = 1e7 + 5;
 9 
10 int n;
11 int vis[maxn];
12 
13 void init()
14 {
15     int m = sqrt(maxn + 0.5);
16     for (int i = 2; i < m; i++)
17     {
18         if (!vis[i])
19         for (int j = i*i; j < maxn; j += i)
20             vis[j] = 1;
21     }
22 }
23 
24 int main()
25 {
26     //freopen("D:\txt.txt", "r", stdin);
27     init();
28     while (cin >> n && n)
29     {
30         for (int i = 3; i < n; i++)
31         {
32             if (!vis[i])
33             {
34                 if (!vis[n - i])
35                 {
36                     printf("%d = %d + %d
", n, i, n - i);
37                     break;
38                 }
39             }
40         }
41     }
42 }