Just My Life & My Work

[C++] 金貝的推測 (Goldbach’s Conjecture)

2011 年 04 月 16 日

這是計算理論Halting Problem的一個例子，任一大於2的偶數n=兩質數之和，例如：

6=3+3
8=3+5
10=3+7
12=5+7
…

此推測在n<10^14時均成立，是否能找出一偶數n!=兩質數之和？

直接用程式來跑[6,100]的結果：

/**
	Theme: Goldbach's Conjecture
	Compiler: Dev C++ 4.9.9.2
	Date: 100/04/16
	Author: ShengWen
	Blog: https://cg2010studio.wordpress.com/
*/
#include<iostream>
using namespace std;
void PrimeM(int n);
const int NUMBER=100;
bool Number[NUMBER]={};
int main(){
	PrimeM(NUMBER);
	bool flag;
	int n1,n2;
	for(int i=6; i<=NUMBER; i+=2){//測試數字從6,8,10,...
		flag=false;
		for(int j=3; 2*j<=i; j+=2){//質數從3,5,7,...
			if(Number[j]==true&&Number[i-j]==true){//如果兩者都為質數
				flag=true;
				n1=j;
				n2=i-j;
			}
			if(flag==true)
				break;
		}
		cout<<i<<'='<<n1<<'+'<<n2<<endl;
	}
	system("pause");
	return EXIT_SUCCESS;
}
void PrimeM(int n){//fill table method
	for(int i=0;i<NUMBER;i++){//initial
		Number[i]=true;
	}
	Number[0]=false;//0不是質數
	Number[1]=false;//1不是質數
	for(int i=2;i<=n;i++){//filter
		for(int j=2;j<i;j++){
			if(i%j==0){
				Number[i]=false;
			}
		}
	}
}

首先必須造出質數表，[1,100]都有true或false的值，接著使用測試數字去跑，若找到兩數之和為測試數字且兩數皆為質數，此測試數字就成立！為了加快速度，測試數字從6,8,10,…開始跳，而質數從3,5,7,…開始找。

程式結果：

6=3+3
8=3+5
10=3+7
12=5+7
14=3+11
16=3+13
18=5+13
20=3+17
22=3+19
24=5+19
26=3+23
28=5+23
30=7+23
32=3+29
34=3+31
36=5+31
38=7+31
40=3+37
42=5+37
44=3+41
46=3+43
48=5+43
50=3+47
52=5+47
54=7+47
56=3+53
58=5+53
60=7+53
62=3+59
64=3+61
66=5+61
68=7+61
70=3+67
72=5+67
74=3+71
76=3+73
78=5+73
80=7+73
82=3+79
84=5+79
86=3+83
88=5+83
90=7+83
92=3+89
94=5+89
96=7+89
98=19+79
100=3+97
請按任意鍵繼續 . . .

可知以上[6,100]偶數皆成立，當然測試數字找到的兩個數可能不只一組，我們可以看WIKI的Goldbach’s conjecture。

GoldbachConjecture

x軸表示測試數字，y軸代表可成立的組合數。

分類：

計算理論, 課業

發表留言

隨意留個言吧：）～

這個網站採用 Akismet 服務減少垃圾留言。進一步了解 Akismet 如何處理網站訪客的留言資料。

標籤雲