哥德巴赫猜想C語言ppt課件

1、1第19章哥德巴赫猜想p 問題描述 p 問題分析及實現(xiàn) p 開發(fā)過程常見問題及解決2第19章哥德巴赫猜想 問題描述 p 問題分析及實現(xiàn) p 開發(fā)過程常見問題及解決3第19章哥德巴赫猜想 問題描述 問題分析及實現(xiàn) p 開發(fā)過程常見問題及解決4第19章哥德巴赫猜想 問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決5哥德巴赫猜想 從哥德巴赫猜想（Gold Bach Conjecture）提出這個猜想至今，許多數(shù)學家都不斷努力想攻克它，但都沒有成功。本章將使用C語言從算法問題入手，并一步步實現(xiàn)一個驗證“猜想”結論正確性的程序。619.1 問題描述 哥德巴赫猜想大致可以分為以下兩個猜想。 二重哥德巴赫猜

2、想：每個不小于6的偶數(shù)都可以表示為兩個奇素數(shù)之和，如下： 6=3+3；8=3+5；10=5+5 三重哥德巴赫猜想：每個不小于9的奇數(shù)都可以表示為三個奇素數(shù)的和，如下： 9=3+3+3；11=3+3+5；13=3+5+5 在這里，我們以二重哥德巴赫猜想作為研究對象，通過編寫C語言程序，來驗證“猜想”的正確性。719.2 問題分析及實現(xiàn) 19.2.1 問題分析 19.2.2 問題實現(xiàn) 19.2.3 程序運行819.2 問題分析及實現(xiàn) 拿到一個要求實現(xiàn)的算法問題，首先要看清、想明、把握每一個細節(jié)。只有這樣，才可以順利地將算法實現(xiàn)。由問題描述：“每個不小于6的偶數(shù)都可以表示為兩個奇素數(shù)之和”，可知，我

3、們要實現(xiàn)的是判斷任何一個大于6的偶數(shù)都可以有兩個素數(shù)相加。以下將仔細地分析問題并實現(xiàn)算法。919.2.1 問題分析 而我們的將要編寫的程序，就是為了驗證哥德巴赫猜想中提到的任何一個偶數(shù)，對大于6的偶數(shù)n可以分解成兩個素數(shù)的和，這個結論是否正確。所以，程序應該可以輸入一個數(shù)，判斷是否為偶數(shù)，將這個偶數(shù)分解成一個小素數(shù)和大素數(shù)。再分別判斷小素數(shù)與大素數(shù)之合是否就等于這個偶數(shù)。而且，需要將結果打印輸出。1019.2.1 問題分析 我們在編程之前，需要明確兩個數(shù)學概念：素數(shù)和偶數(shù)。 素數(shù)就是質數(shù)，指在一個大于1的自然數(shù)中，除了1和此整數(shù)自身外，沒法被其他自然數(shù)整除的數(shù)。換句話說，只有兩個正因數(shù)（1和數(shù)

4、自身）的自然數(shù)即為素數(shù)。 偶數(shù)就是能被2整除的自然數(shù)，如2、4、6、8。 根據題目，要求是奇素數(shù)，即這個素數(shù)不可以是2，一定要大于2。我們需要劃分以下兩個子模塊。 判斷一個數(shù)是否為素數(shù)。 判斷并分解大小素數(shù)的和是否等于需判斷的偶數(shù)。1119.2.2 問題實現(xiàn) 1. 判斷輸入的數(shù)字是否是素數(shù) 對于一個任何自然數(shù)，如何判斷他是素數(shù)呢？如果這個自然數(shù)n，它存在兩個因數(shù)，乘積等于n，要么兩個因數(shù)一個是小于 、 一個大于 ，要么兩個因數(shù)都等于 。那么，根據這個思路，代碼如下（代碼19-1.txt）。nnn1219.2.2 問題實現(xiàn)01 /*測試n是否是素數(shù)。如果是，返回1，否則返回0 */02 int

5、IsPrimer(unsigned long n)03 04 unsigned long i;05 unsigned long nqrt;06 if (n = 2)07 return 1;08 if (n = 1 | n%2 = 0)09 return 0;10 /*如果它存在兩個因數(shù)，乘積等于n，要么兩個因數(shù)一定一個小于根號n，一個大于根號n要么兩個因數(shù)都等于根號n*/11 nqrt = (unsigned long)sqrt(n);12 for(i=2; i=nqrt; i+=1)13 14 if (n%i = 0)15 return 0;16 17 return 1; 18 1319.2

6、.2 問題實現(xiàn) 2. 將數(shù)偶數(shù)分解成兩個素數(shù)，并判斷“猜想”結論是否成立。 取一個數(shù)i，從最小素數(shù)開始到這個偶數(shù)的一半大小進行判斷，當i為素數(shù)同時n-i也是素數(shù)時，這時猜想結論成立，否則結論不成立。代碼如下（代碼19-2.txt）。1419.2.2 問題實現(xiàn)01 int IsRight(unsigned long n, unsigned long *tmpNumA, unsigned long *tmpNumB)02 03 unsigned long i;04 unsigned long half;05 half = n/2;06 for (i=3; i= 6 & (number %

7、2 = 0)10 11 if (IsRight(number, &a, &b)12 13 printf(哥德巴赫猜想對此數(shù)是正確的。n);14 printf(%lu = %lu + %lun, number, a, b);15 16 else17 18 printf(%lu，哥德巴赫猜想對此數(shù)是錯誤！, number);19 20 21 while(number != 0);22 23 return 0;24 1719.2.3 程序運行1819.3 開發(fā)過程常見問題及解決 開發(fā)過程常見問題及解決辦法如下，僅供參考。 如果出現(xiàn)“warning C4013: sqrt undefined; assuming extern returning int”的編譯警告，通常需要在程序開頭添加數(shù)學函數(shù)頭文件“#include