【C语言】验证哥德巴赫猜想
慕雪年华

问题来源

这是学校的一个作业,原题如下

image

题目先给出了哥德巴赫猜想的背景知识(我还真不知道)

2000以内的正偶数都能分解成两个质数(素数)之和

题目要求

下面来梳理一下题目的要求:

  • 输出样式为a=b+c,使用%4d=%4d+%4d输出
  • 每行输出4个,每行最后一个输出无空格
  • 每个偶数只需要一个结果即可(后续较大的偶数有很多种解)

弄懂了题目要求,下面就来一步一步写代码


如何判断素数?

在上篇博客里面提到了如何判断素数==>【链接】,这里不再赘述

我们需要搞定的是判断是那两个素数b、c相加等于我们需要的那个数a

因为需要多次判断,这里我们使用自定义函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int SuShu(int a)
{
if (a == 2)
{
return 1;
}
int j = 0;
for(j = 2; j <=sqrt(a); j++)
{
if (a % j == 0)
{
return 0;
}
}
return 1;
}

为什么是return1和0呢?

因为在写这段代码的时候,我本来是想判断之后返回一个素数,但是这个方法效率太低

而且写到后面我自己都不会写了,遂放弃。


主函数

最终实现形式:n=a+(n-a)

在自定以函数里面返回的值是1和0

主函数里面就需要内容来接收

1
if (SuShu(a) && SuShu(n - a))//判断a和n-a是否都是素数

同时我们需要完成打印4行换一行,以及每行最后一个不能有空格的要求

这时候直接在printf语句里面加空格已经不够了

需要用到判断语句,判断已经打印了几个等式

1
2
3
4
5
6
7
8
9
10
11
12
13
if (SuShu(a) && SuShu(n - a))
{
printf("%4d=%4d+%4d", n, a, n - a);
count++;//每打印一次就++一次
if (count % 4 == 0)
{ //打印4次后打印一个换行符
printf("\n");
}
else
{ //不够4次,需要打印空格
printf(" ");
}
}

素数判断的部分我们已经写完了

接下来要写的是一个for循环,让n从4开始一直+到2000

另外,同【如何判断素数】博客中的开平方法一样

在验证哥德巴赫猜想的时候,若a=b+c,b和c中肯定有一个数小于或等于a/2

在写a的for循环的时候,我们可以让判断条件a<=n/2,而不是a<n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for (n = 4; n <= 2000; n+=2)
{
for (int a = 2; a <= n/2 ; a++)
{ //在之前我们并没有定义a,需要在for循环里加上int
if (SuShu(a) && SuShu(n - a))
{
printf("%4d=%4d+%4d", n, a, n - a);
count++;
if (count % 4 == 0)
{
printf("\n");
}
else
{
printf(" ");
}
}
}

}

到这里,我们的主函数也完成啦!

完整代码+效果演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <math.h>

int SuShu(int a)
{
if (a == 2)
{
return 1;
}
int j = 0;
for(j = 2; j <=sqrt(a); j++)
{
if (a % j == 0)
{
return 0;
}
}
return 1;
}
//验证哥德巴赫猜想,输出4到2000的偶数
//每个偶数的结果只输出一次
int main()
{
int n = 0;
int count = 0;
for (n = 4; n <= 2000; n+=2)
{
for (int a = 2; a <= n/2 ; a++)
{
if (SuShu(a) && SuShu(n - a))
{
printf("%4d=%4d+%4d", n, a, n - a);
count++;
if (count % 4 == 0)
{
printf("\n");
}
else
{
printf(" ");
}
break; //只打印一种情况
}
}

}
return 0;
}

细心的你肯定注意到,在main函数中判断素数的语句里多了一个break,它的作用是什么呢?

如果没有break,结果如下:

代码会将符合条件的素数相加全部打印出来

这显然不符合每个偶数的结果只输出一次的要求

image

但在加了break这个断点之后

代码的结果就和题目要求的一样了

image


写代码中的误解

在最终提交代码的时候,我的代码格式出错了

原因是我在printf语句里面加多了两个空格,如下:

1
printf("%4d= %4d+ %4d", n, a, n - a);

为什么我会想当然的多加两个空格呢?

因为题目所给的输出样例,让我误以为=和+之间都有两个空格

image

实际上这里并没有空格,它的“空格”是printf中的%4d造成的

代码给这里留了4个数字的位置,但是大多都只有一个数字和两个数字

于是它们前面就会有3或者2个留给数字的空,让我误以为这里有空格

基础不牢,地动山摇!


总结

通过这道题,我复习了循环和自定义函数的写法,也获得了哥德巴赫猜想的新知识

多刷刷题总是好的

希望这篇博客对你有帮助!