Goldbach's conjecture到4 * 10^18都是對的,
所以在1000000的範圍內,不會有Goldbach's conjecture is wrong的output。
所以就從3, 5, 7, ...一直往上找,一定會存在一組質數使得n = prime1 + prime2。
/* ACM 543 Goldbach's Conjecture * mythnc * 2011/11/04 15:28:29 * run time: 0.164 */ #include <stdio.h> #define TRUE 1 #define FALSE 0 int prime(int); int main(void) { int n, i; while (scanf("%d", &n) && n != 0) for (i = 3; i < n; i += 2) if (prime(i) == TRUE && prime(n - i) == TRUE) { printf("%d = %d + %d\n", n, i, n - i); break; } return 0; } /* prime: if n is prime, return TRUE, * else return FALSE */ int prime(int n) { int i; for (i = 3; i * i <= n; i += 2) if (n % i == 0) return FALSE; return TRUE; }
沒有留言:
張貼留言