《C程序设计》（夏宝岚） [相关] [031] 判断m是否是素数[相关] [066] 筛选法求素数 哥德巴赫猜想的命题之一是:任意一个大于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+38=3+510=3+712=5+714=3+1116=3+1318=5+1320=3+1722=3+1924=5+1926=3+2328=5+2330=7+2332=3+2934=3+3136=5+3138=7+3140=3+3742=5+3744=3+4146=3+4348=5+4350=3+4752=5+4754=7+4756=3+5358=5+5360=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+38=3+510=3+712=5+714=3+1116=3+1318=5+1320=3+1722=3+1924=5+1926=3+2328=5+2330=7+2332=3+2934=3+3136=5+3138=7+3140=3+3742=5+3744=3+4146=3+4348=5+4350=3+4752=5+4754=7+4756=3+5358=5+5360=7+53=================== ★ 另外,这是个验证程序,即事实已经存在,t在小于x的范围内必有满足条件的值,所以不会出现t大于x的情况,因此程序中没有做此判断。

评论