设为首页 加入收藏

TOP

C语言验证哥德巴赫猜想代码及及解析
2018-11-24 22:08:33 】 浏览:27
Tags:语言 验证 哥德 巴赫 猜想 代码 解析

问题描述


2000以内的不小于4的正偶数都能够分解为两个素数之和(即验证歌德巴赫猜想对2000以内的正偶数成立)。


问题分析


根据问题描述,为了验证歌德巴赫猜想对2000以内的正偶数都是成立的,要将整数分解为两部分,然后判断分解出的两个整数是否均为素数。若是,则满足题意,否则应重新进行分解和判断。


算法设计


定义一个函数,函数名设为fun,在其中判断传进来的实际参数(设为n(n≥2)),是否为素数,如果是素数则返回1,否则返回0。需要注意的是,在所有偶数中,只有2是唯一的素数。因此,在函数fun中,可以分为以下4种情况来判断:


 在主函数中,使用循环结构,每输入一个数据就处理一次,直到遇到文件结束符则终止输入。下面详述主函数中处理数据的过程。


 由于已经对输出做了限定,即当输出结果时,如果有多组解,则输出a最小的那组解。显然,对每个读入的数据a必然小于或等于n/2,因此,定义循环变量i,使其从2?n/2进行循环,每次循环都做如下判断:fun(i)&&fun(n-i)是否为1。


 如果fun(i)&&fun(n-i)=1,则表示fun(i)=1同时fun(n-i)=1。由fun()函数的定义可知,此时i和n-i都为素数,又由于i是从2?n/2按由小到大的顺序来迭代的,因此(i,n-i) 是求出的一组解,且该组解必然是所有可能解中a值最小的。


 还需要注意的是,由于除了2以外的偶数不可能是素数,因此i值的可能取值只能是2和所有的奇数。


下面是完整的代码:


#include<math.h>
#include<stdio.h>
int fun(int n)
{
    int i;
    if(n==2)
        return 1;  /*n是2,返回1*/
    if(n%2==0)
        return 0;  /*n是偶数,不是素数,返回0*/
    for(i=3; i<=sqrt(n); i+=2)
        if(n%i==0)
            return 0;  /*n是奇数,不是素数,返回0*/
    return 1;  /*n是除2以外的素数返回1*/
}
int main()
{
    int n, i, ok;
    while(scanf("%d",&n)!=EOF)
    {
        ok=0;  /*进入循环前先置标志位*/
        for(i=2; i<=n/2; i++)
        {
            if( fun(i) )
                if( fun(n-i) )
                {
                    printf("%d %d\n", i, n-i);  /*i和n-i都是素数,则打印*/
                    ok=1;
                }
            if(i!=2)
                i++;
            if(ok)
                break;  /*已打印出所需要的输出结果,跳出循环*/
        }
    }
    return 0;
}


运行结果:


100
3 97
5
2 3
99
2 97
1000
3 997


C语言验证哥德巴赫猜想代码及及解析



编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Visual Studio 2017中使用SourceL.. 下一篇SpringMVC处理参数中的枚举类型..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }