#include #include #define MAX 1000000 int prim [MAX]; int a [MAX]; int b [MAX]; int sieb [MAX]; int k; int n = 0; FILE *input; void GetPrim () { int i,j; for (i = 0; i < MAX; i++) { sieb [i] = 1; } for (i = 2; i < MAX; i++) { if (sieb [i]) { prim [n++] = i; for (j = i; j < MAX; j+=i) { sieb [j] = 0; } } } } int ReadCase () { fscanf (input, "%d", &k); if (feof (input)) return 0; if (k == 0) return 0; return 1; } int FindNearest (int m, int u, int v) { int i; while (m + 1 < u) { i = (m + u) /2; if (prim [i] < v) m = i; else if (prim [i] > v) u = i; else return i; } if (prim [i] == v) return i; return m; } void CreateAll () { int i, j; int ma = n - 1; int z = 0, e = (MAX - 6) / 2 ; for (j = 1; j < n; j++) { if (prim [j] + prim [j] < MAX) { for (i = ma; i >= j; i--) { if (prim [j] + prim [i] > MAX) ma = i; if (sieb [prim [i] + prim [j]] == 0) { z++; sieb [prim [i] + prim [j]] = 1; a [prim [i] + prim [j]] = prim [i]; b [prim [j] + prim [i]] = prim [j]; if (z == e) return; } } } } } void Solve () { if (sieb [k] == 0) printf ("Goldbach's conjecture is wrong.\n"); else { printf ("%d = %d + %d\n", k, b [k], a [k]); } } void SolveCase () { int i, j; int m = 1; for (i = n-1; i >= 1; i--) { if (prim [i] + prim [i] < k) { printf ("Goldbach's conjecture is wrong.\n"); return; } if (prim [i] < k) { m = FindNearest (m, i, k - prim [i]); if (prim [m] + prim [i] == k) { printf ("%d = %d + %d\n", k, prim [j], prim [i]); return; } } /* for (j = m; j <= i; j++) { if (prim [i] + prim [j] > k) j = i; if (prim [i] + prim [j] < k) m = j; if (prim [i] + prim [j] == k) { printf ("%d = %d + %d\n", k, prim [j], prim [i]); return; } }*/ } printf ("Goldbach's conjecture is wrong.\n"); } int main () { input = fopen ("goldbach.in","r"); assert (input != 0); GetPrim (); CreateAll (); while (ReadCase ()) Solve (); fclose (input); return 0; }