验证“哥德巴赫猜想”思路分析 |
您所在的位置:网站首页 › 验证哥德巴赫猜想程序框图 › 验证“哥德巴赫猜想”思路分析 |
数学领域著名的“哥德巴赫猜想”的大致意思是:任何一个大于2的偶数总能表示为两个素数之和。比如:24=5+19,其中5和19都是素数。本实验的任务是设计一个程序,验证20亿以内的偶数都可以分解成两个素数之和。 输入格式:输入在一行中给出一个(2, 2 000 000 000]范围内的偶数N。 输出格式:在一行中按照格式“N = p + q”输出N的素数分解,其中p ≤ q均为素数。又因为这样的分解不唯一(例如24还可以分解为7+17),要求必须输出所有解中p最小的解。 输入样例: 24 输出样例: 24 = 5 + 19先理清思路:一个大于2的偶数由两个素数相加得到, 先考虑将这个偶数拆分,再判断拆分的两个数是否是素数 N=24,用一个循环从i=2开始,p=i,q=N-i,当p、q同时为素数时就可以输出了 iN-i Npqp+q2222432124420245192461824717248162491524101424111324 #include int prime(int k) //判断是否是素数的函数 { int i; int flag = 1; for (i = 2;i < k;i++) { if (k % i == 0) { flag = 0; break; } } if (flag) //返回是否是素数 return 1; else return 0; } int main() { int N, p, q, i; scanf("%d", &N); for (i = 2;i < N / 2;i++) //一个循环进行分解,N的和是第一个数+倒数第2个数的和:1+N-1、2+(N-2)...以此类推,这里的循环数只需进行N的一半 { //因为N本身是偶数,偶数的一半不可能是素数,就不包括对N/2的循环 int flag1 = 1, flag2 = 1; //此处判断是否是素数 p = i; q = N - i; if (i == 2) //此处是因为2是素数要单独拿出来,不用进行素数函数的判断 { flag2 = prime(q); //因此此处只需判断q是否是素数 } else { flag1 = prime(p); flag2 = prime(q); } if (flag1 && flag2) //p、q同时为素数时就可以输出了 { printf("%d = %d + %d", N, p, q); break; } } return 0; }又思考了一下,在for循环那里的i++可以改成:i=(2*i-1),循环次数减少一半,因为后面分解出来的p和q是偶数不会是素数 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |