用C语言编程验证 “ 哥德巴赫猜想 ”_loon

---

前言

哥德巴赫猜想是数论中存在最久的未解问题之一。其陈述为：任一大于 2 的偶数都可表示成两个质数之和，例如44=3+41=7+37=13+31。

接下来，我们将用C语言编程验证哥德巴赫猜想，并在其基础上使用以空间换时间的方法来提高算法效率。

---

一、素数表

要想验证哥德巴赫猜想，就必须先要编程出可以得到素数的函数，在这里我们使用自定义函数 prime() 判断一个数是否为素数，进而打印100以内的全部素数：

#include <stdio.h>
#include <math.h>

int prime(int n); //函数声明，判断n以是否为素数 

int main()
{
	for (int i = 2; i < 100; i ++)
		if (prime(i)) //if(prime(i)!=0：根据函数调用返回值来做出相应判断 
			printf("%%6d", i);
			
	return 0;
} 

// 判断素数函数，是返回1，否返回0 
int prime(int n)
{
	if (n == 1) //1不是素数 
		return 0;
		
	int temp = (int)sqrt(n);
	for (int i = 2; i <= temp; i++)
		if (n %% i == 0)
			return 0;
			
	return 1; //n是素数 
}
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

二、验证哥德巴赫猜想（基础版）

要想验证哥德巴赫猜想，我们可以调用上一个程序中的自定义函数 prime() ，通过枚举法的思想来验证：
要把偶数分解成两个素数的和，通过循环枚举第一个加数 i ，枚举范围是 3 到 even/2 之间的奇数（even就是要验证的偶数），调用函数 prime() 判断 i 和 even/2 是否都为素数，若不都是素数，则枚举下一个加数，若都是素数，则输出该组合。

实现过程如下：

1. 声明变量 even , i；
2. 读入偶数 even 的值；
3. i 从 3 到 even/2 循环，重复下列操作：若 prime(i) 和 prime(even-i) 同为真，则输出这两个值。

#include <stdio.h>
#include <math.h>

int prime(int n);    //函数声明，判断素数 

int main()
{
	int even;
	
	scanf("%%d", &even);
	for (int i = 3; i <= even/2; i += 2)
		if (prime(i) && prime(even-i))
			printf("%%d %%d
", i, even-i);
			
	return 0;
} 

// 判断素数，若是返回1，否则返回0 
int prime(int n)
{
	if (n == 1)
		return 0;
	
	int temp = (int)sqrt(n);
	for (int i = 2; i <= temp; i ++)
		if (n %% i == 0)
			return 0;
	
	return 1;
}
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

三、筛选法求素数

以空间换时间是一种很常见的一种提高算法效率的方法。这是一种思想，不是一种算法。这种思想的主要应用有以下两种：第一种是将之前计算的结果保存下来，方便当前计算之用，从而降低计算量；第二种是将所有步骤都需要用到的公共计算部分事先计算好，等真正计算时，只需调用事先计算好的结果就可以了。

素数在很多应用领域都有很重要的用途，寻找一个高效的算法十分重要。例如找出 10000 以内的素数可能仅仅是为某个程序做的准备工作，为提高程序的效率，我们都希望在尽可能短的时间内完成。那么，下面就来介绍一个经典算法——筛选法求素数。

所谓筛选法是指从小到大去筛选一个已知素数的所有倍数。以筛选法求 10000 以内的素数为了，根据素数 2 可筛去 4、6、8、··· 、9998、10000 等数，然后根据素数 3 可筛去 9、6、12、15、··· 、9999 等数，由于 4 已经被筛去了，下一个用于筛选的素数是 5 ······ 以此类推，最后剩下的就是 10000 以内的素数。

应用筛选法求素数，为了方便实施 “划去” 操作，应设置数组 isPrime 。每一数组元素 isPrime[i] 赋初值 1 。如果 i 为某数的倍数则应划去，通常将 isPrime[i] 赋值 0。最后，值不为 0 （即没有划去）的元素对应的下标即所求素数。

#include <stdio.h>
#include <math.h>

#define N 10000

void prime(int n); //调用筛选素数函数 
int isPrime[N+1];

int main()
{
	prime(N);
	for (int i = 0; i <= N; i ++) //输出 10000 以内的所有素数 
		if (isPrime[i])
			printf("%%5d", i);
	
	return 0;
} 

// 筛选从2到n之间的素数，筛选结果存入数组isPrime 
void prime(int n)
{
	for (int i = 0; i <= n; i ++) //将isPrime数组元素初始化为1 
		isPrime[i] = 1;
	
	isPrime[0] = isPrime[1] = 0; //0和1不是素数 
	int temp = (int)sqrt(n);
	
	for (int i = 2; i <= temp; i ++)
		if (isPrime[i]) //筛选掉素数的整数倍 
			for (int j = 2*i; j <= n; j += i)
				isPrime[j] = 0;
}
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

四、验证哥德巴赫猜想（加强版）

在上面，我们已经完成了一个验证哥德巴赫猜想的程序，但那只是一个基础版本，下面我们就来使用筛选法优化其成为加强版。

验证方法如下：输入两个整数 a, b（5<a<b<10000），程序将区间[a, b] 中所有偶数都表示成两个素数之和。若某个偶数有多种素数拆分方法，则只输出第一个加数最小的拆分方法。

若 a=38，b=44，则输出为：
38 = 7 + 31
40 = 3 + 37
42 = 5 + 37
44 = 3 + 41

#include <stdio.h>
#include <math.h>

#define N 10000

void SeparateEven(int n); //将n分成两个素数的和
void prime(int n); //判断素数

int isPrime[N+1];

int main()
{
	int a, b;
	
	scanf("%%d%%d", &a, &b);
	if (a %% 2 != 0)
		a ++;
	prime(N); //调用筛选素数函数
	
	for(int i = a; i <= b; i += 2)
		SeparateEven(i); //将i表示为两个素数之和 
		
	return 0;
} 

// 将n表示为两个素数之和 
void SeparateEven(int n)
{
	for (int i = 3; i <= n/2; i ++)
		if (isPrime[i] && isPrime[n-i]) //若两个加数都是素数，则输出n的拆分 
	{
		printf("%%d = %%d + %%d
", n, i, n-i);
		break;
	}
}


// 筛选从2到n之间的素数，筛选结果存入数组 isPrime 
void prime(int n)
{
	for (int i = 0; i <= n; i ++)
		isPrime[i] = 1; //将isPrime数组元素初始化为1 
		
	isPrime[0] = isPrime[1] = 0; //0和1不是素数 
	int temp = (int)sqrt(n);
	
	for (int i = 2; i <= temp; i ++)
		if (isPrime[i]) //筛去素数的整数倍 
			for (int j = 2*i; j <= n; j += i)
				isPrime[j] = 0;
}
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
49
50
51

---

总结

关于素数吧，从学习编程开始，就一直对其进行优化，从一开始的逐字检查，再到遍历到 sqrt(n) ，最后完成筛选法，这一步步下来，收获颇丰啊，想到以后很可能会经常用到，就学一篇笔记来总结下好了，哈哈。