20111104

ACM 543 Goldbach's Conjecture

wiki可知,
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;
}

沒有留言: