《C程序设计》（夏宝岚）

哥德巴赫猜想的命题之一是:任意一个大于6的偶数必定由两个素数组成,试编写程序,验证并输出6至60以内的所有偶数的素数之和表达式。

    由于每拆分一个偶数需要两次判断素数，因此程序中首先定义函数prime()，用于素数的判断，另外设计函数sumprime(int x)，通过调用prime函数将一个偶数拆分成两个素数之和的表达式。

#include <stdio.h>

int prime(int x)
{
    int i;
    for (i = 2; x % i != 0; i++)
        ;
    return x == i ? 1 : 0;
}
void sumprime(int x)
{
    int t1, t2;
    t1 = 1;
    do
    {
        for (;;)
        {
            if (t1 <3 )
                t1 = t1 + 1;
            else
                t1 = t1 + 2;
            if (prime(t1))
                break;
        }
        t2 = x - t1;
    }while(!prime(t2));
    printf("%d=%d+%d\n", x, t1, t2);
}
void main()
{
    int a;
    for(a = 6; a <= 60; a += 2)
        sumprime(a);
}

运行结果（VC）：
===========================
6=3+3
8=3+5
10=3+7
12=5+7
14=3+11
16=3+13
18=5+13
20=3+17
22=3+19
24=5+19
26=3+23
28=5+23
30=7+23
32=3+29
34=3+31
36=5+31
38=7+31
40=3+37
42=5+37
44=3+41
46=3+43
48=5+43
50=3+47
52=5+47
54=7+47
56=3+53
58=5+53
60=7+53
===========================

★ 其实有了判断素数函数后,主要问题就是如何将某大于6的偶数分解成两个素数,书中这个程序从将这个数拆成t1,t2两个数,t1由1开始增(用do-while结构1不在判断范围内),增为一个素数时,再判断t2是不是素数,如果是,验证完毕,如果不是,t1继续增。其实2已知为最小素数，因为4之后的偶数肯定都不是素数，所以以3为分界，后面直接将偶数跳过，即t1增2就行了。

既然已知2为最小素数，那为什么不由2开始呢？下面是我按我自己的思路写的，拆分和判断的方法稍有不同，在大于3时没有直接隔2递增，而始终是增1的，增完后判断是否为素数，如果不是素数，再加1，实际上就是在循环中对每个偶数都做判断，而且在判断后加1，效率上不如书中的，循环判断的次数也多了近一倍：

#include <stdio.h>

int prime(int x)
{
    int i;
    for (i = 2; x % i != 0; i++)
        ;
    return x == i ? 1 : 0;
}
void sumprime(int x)
{
    int t = 2;
    while(!prime( x - t))
    {
        t++;
        if(!prime(t))
            t++;
    }
    printf("%d=%d+%d\n", x, t, x - t);
}
void main()
{
    int a;
    for(a = 6; a <= 60; a += 2)
        sumprime(a);
}

运行结果（VC）：
===================
6=3+3
8=3+5
10=3+7
12=5+7
14=3+11
16=3+13
18=5+13
20=3+17
22=3+19
24=5+19
26=3+23
28=5+23
30=7+23
32=3+29
34=3+31
36=5+31
38=7+31
40=3+37
42=5+37
44=3+41
46=3+43
48=5+43
50=3+47
52=5+47
54=7+47
56=3+53
58=5+53
60=7+53
===================

★ 另外,这是个验证程序,即事实已经存在,t在小于x的范围内必有满足条件的值,所以不会出现t大于x的情况,因此程序中没有做此判断。

评论