⽤C语⾔编程验证“哥德巴赫猜想”
⽂章⽬录
前⾔
哥德巴赫猜想是数论中存在最久的未解问题之⼀。其陈述为：任⼀⼤于 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);
return0;
}
// 判断素数函数，是返回1，否返回0
int prime(int n)
{
if(n ==1)//1不是素数
return0;
int temp =(int)sqrt(n);
for(int i =2; i <= temp; i++)
if(n % i ==0)
return0;
return1;//n是素数
}
⼆、验证哥德巴赫猜想（基础版）
要想验证哥德巴赫猜想，我们可以调⽤上⼀个程序中的⾃定义函数 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\n", i, even-i);
return0;
}
// 判断素数，若是返回1，否则返回0
int prime(int n)
{
if(n ==1)
return0;
int temp =(int)sqrt(n);
for(int i =2; i <= temp; i ++)
if(n % i ==0)
return0;
return1;
}
三、筛选法求素数
以空间换时间是⼀种很常见的⼀种提⾼算法效率的⽅法。这是⼀种思想，不是⼀种算法。这种思想的主要应⽤有以下两种：第⼀种是将之前计算的结果保存下来，⽅便当前计算之⽤，从⽽降低计算量；第⼆种是将所有步骤都需要⽤到的公共计算部分事先计算好，等真正计算时，只需调⽤事先计算好的结果就可以了。
素数在很多应⽤领域都有很重要的⽤途，寻⼀个⾼效的算法⼗分重要。例如出 10000 以内的素数可能仅仅是为某个程序做的准备⼯作，为提⾼程序的效率，我们都希望在尽可能短的时间内完成。那么，下⾯就来介绍⼀个经典算法——筛选法求素数。
所谓筛选法是指从⼩到⼤去筛选⼀个已知素数的所有倍数。以筛选法求 10000 以内的素数为了，根据素数 2 可筛去 4、6、8、··· 、9998、10000 等数，然后根据素数 3 可筛去 9、6、12、15、··· 、9999 等数，由于 4 已经被筛去了，下⼀个⽤于筛选的素数是5 ······ 以此类推，最后剩下的就是 10000 以内的素数。
#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);
return0;
}
// 筛选从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;
}
#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表⽰为两个素数之和
return0;
}
// 将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", 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 ++)c语言如何去学
if(isPrime[i])//筛去素数的整数倍
for(int j =2*i; j <= n; j += i)
isPrime[j]=0;
}
总结
关于素数吧，从学习编程开始，就⼀直对其进⾏优化，从⼀开始的逐字检查，再到遍历到 sqrt(n) ，最后完成筛选法，这⼀步步下来，收获颇丰啊，想到以后很可能会经常⽤到，就学⼀篇笔记来总结下好了，哈哈。