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

栏目: C · 发布时间: 2年前

来源: www.linuxidc.com

内容简介:2000以内的不小于4的正偶数都能够分解为两个素数之和(即验证歌德巴赫猜想对2000以内的正偶数成立)。根据问题描述,为了验证歌德巴赫猜想对2000以内的正偶数都是成立的,要将整数分解为两部分,然后判断分解出的两个整数是否均为素数。若是,则满足题意,否则应重新进行分解和判断。定义一个函数,函数名设为fun,在其中判断传进来的实际参数(设为n(n≥2)),是否为素数,如果是素数则返回1,否则返回0。需要注意的是,在所有偶数中,只有2是唯一的素数。因此,在函数fun中,可以分为以下4种情况来判断:

本文转载自:https://www.linuxidc.com/Linux/2018-11/155449.htm,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有。

问题描述

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

问题分析

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

算法设计

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

  • n=2,是素数,返回1。
  • n是偶数,不是素数,返回0。
  • n是奇数,不是素数,返回0。
  • n≠2,是素数,返回1。

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

由于已经对输出做了限定,即当输出结果时,如果有多组解,则输出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语言验证哥德巴赫猜想代码及及解析

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址: https://www.linuxidc.com/Linux/2018-11/155449.htm


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

关注码农网公众号

关注我们,获取更多IT资讯^_^


查看所有标签

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

互联网+秋叶课堂:我的网课创业

互联网+秋叶课堂:我的网课创业

秋叶 / 北京:机械工业出版社 / 2016-3-1 / 39.0

在线教育被很多人视为 “互联网+”创业热潮中的下一个风口,越来越多的老师和创业者选择在线教育创业。本书作者秋叶老师2013年双11正式带一帮小伙伴开始在线教育创业,在短短两年内“从0到1”,累计做到了超500万元的销售业绩,成为国内Office领域在线教育运营最成功的团队之一。在这本书中秋叶老师结合自己的实战经历,向各位完整剖析了两年创业的真实复盘思考,是一本值得在线教育创业同行入手的必读书。 ......一起来看看 《互联网+秋叶课堂:我的网课创业》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

URL 编码/解码
URL 编码/解码

URL 编码/解码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试