4_goldbachs_conjecture.c

证明Goldbach s Conjecture是我第二个小作业,也可以计算Goldbach s Conjecture

/**
 * 上机作业4：Goldbach's Conjecture
 * http://cms.hit.edu.cn/mod/assignment/view.php?a=130
 * http://acm.hit.edu.cn/ojs/show.php?Proid=1459&Contestid=0
 *
 * Copyright: Public domain
 * Author: Sunner Sun
 * Organization: 哈尔滨工业大学(Harbin Institute of Technology)
 * Date: 2006-11-14-14.35
 */

#include <stdio.h>
#include <math.h>
#include <assert.h>

int IsPrime(unsigned long n);

int main()
{
    int num;
    int i;
    int found;

    while ( scanf("%d", &num) == 1 && num != 0 )
    {
        found = 0;
        for (i = 3; i <= num; i += 2)
        {
            if ( IsPrime(i) && IsPrime(num - i) )   /* &&只算一半的特性保证IsPrime()不会被无谓调用 */
            {
                found = 1;
                break;
            }
        }

        if (found)
            printf("%d = %d + %d\n", num, i, num - i);
        else
            printf("Goldbach's conjecture is wrong.\n");
    }

    return 0;
}

/**
 * 判断一个数是否为素数
 *
 * @param n 被判定的数。必须为正数
 * @return 如果是素数，返回非0值；否则返回0
 */
int IsPrime(unsigned long n)
{
    unsigned long i;
    unsigned long maxFactor;

    assert(n > 0);

    if (n == 2)
    {
        return 1;
    }
    else if ( n == 1 || n % 2 == 0 )    /* 所有偶数和1都不是素数 */
    {
        return 0;
    }

    maxFactor = sqrt(n) + 1;            /* +1确保平方根在处理范围内 */
    for(i = 3; i <= maxFactor; i += 2)
    {
        if (n % i == 0)
        {
            return 0;
        }
    }

    return 1;
}