題目：算法時間性能的經(jīng)驗分析（驗證哥巴赫猜想）
驗證哥德巴赫猜想。統(tǒng)計其關(guān)鍵語句的執(zhí)行次數(shù)。并繪制規(guī)模-執(zhí)行次數(shù)散點圖。
(Goldbach Conjecture)猜想:即任一大于2的偶數(shù)都可寫成兩個質(zhì)數(shù)之和。請驗證這個對于較大的偶數(shù)都是成立的。
算法:goldbach(n)
描述∶算法驗證對于小于等于n的偶數(shù)，歌德巴赫猜想都是成立的。注意，goldbach(200)并非驗證200可以拆分成兩個質(zhì)數(shù)的和，而是驗證對于所有≤n的偶數(shù)，都可以拆分成兩個質(zhì)數(shù)的和。
輸入:整數(shù)n
輸出:1表示成立;0表示猜想有誤
注1:用excel繪制散點圖，excel可以打開csv格式的文件。
注2∶csv(comma seperated values)是如下格式的文件。
文件位置：

public class Goldbach {/*** @param args* @throws IOException*/public static int cnt;public static List list = new ArrayList();public static int ARR_SIZE = 2500;public static int[] arr = new int[ARR_SIZE];public static void main(String[] args) throws IOException {Writer file = new FileWriter("diagram.csv");file.write("n,times\n");String line;cnt = 0;primes();for (int n = 200; n <= 5000; n += 50) {int temp = cnt;cnt = 0;if(n == 200){cnt += temp;}if (passGoldConj(n)) {line = Integer.toString(n) + "," + Integer.toString(cnt) + "\n";file.write(line);} else {System.out.println("Goldbach conjuction doesn't hold in our test");break;}}file.close();}public static boolean isPrime(int n) {if (list.indexOf(n) != -1){return true;}return false;}public static boolean passGoldConj(int n) {int k = 0;for (int i = 4; i <= n; i += 2 ){cnt++;for(int j = 2; j < i; j++) {cnt++;if (isPrime(j) && isPrime(i - j)) {k++;break;}}}if (k == (n/2 - 1)) {return true;}return false;}//這里使用的是篩選法求質(zhì)數(shù)因子public static void primes(){arr[0] = 2;for (int i = 1, j = 3; i < ARR_SIZE; i++,j += 2){cnt++;arr[i] = j;}for (int i = 1; i < ARR_SIZE; i++) {cnt++;if (Math.pow(arr[i], 2) <= ARR_SIZE*2 && arr[i] != 0){int j, temp;temp = arr[i];//相比日常的篩選法，改進(jìn)了一下for (j = temp * temp; j <= ARR_SIZE*2; j += 2*temp) {cnt++;int index = (j-1)/2;arr[index] = 0;}}}for (int i = 0; i < ARR_SIZE; i++) {cnt++;if (arr[i] != 0) {list.add(arr[i]);}} // System.out.println(list); // System.out.println(list.size());} }

時間復(fù)雜度是近乎O(n)，線性的，但是求第一個質(zhì)數(shù)是很廢時間的，因為我是將某數(shù)以內(nèi)的所需質(zhì)數(shù)全部求出。

純屬記錄分享，會有更好的方法

總結(jié)

以上是生活随笔為你收集整理的验证哥巴赫猜想的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。