聯成電腦技術論壇

 找回密碼
 註冊
搜索
查看: 1273|回復: 34

[作品] 印出質數序列

[複製鏈接]
發表於 2012-9-9 01:12:54 | 顯示全部樓層 |閱讀模式
[i=s] 本帖最後由 ccyvision 於 2012-9-9 01:40 編輯 [/i]

最近無聊想試試練習 "直觀寫作法",就是像寫文章一樣把程式打出來,所以就挑了一個很古老的題目: 求質數,趁老媽煮飯的時間把它寫出來。
以下是練習的結果

import javax.swing.JOptionPane;

public class PrimeNumber {

        static int NUM_OF_PRIME = 500;
        static int[] prime = new int[NUM_OF_PRIME];

        public static void main(String[] args) {

                String msg = "2, 3, ";
                prime[0] = 2;
                prime[1] = 3;
                prime[2] = 5;
                for (int i = 3; i < NUM_OF_PRIME; i++) {
                        prime [i] = nextPrime (i-1);
                        msg += prime[i] + ", ";
                        if (i % 20==0) msg+="\n";
                }
                JOptionPane.showMessageDialog(null, msg);
        }

        static int nextPrime(int index) {
                int p = prime[index];
                int maxTest = 0;
                int di;
                boolean flag = false, negFlag;
                do {  // next p
                        negFlag = false;
                        do p++;
                        while (p % 2 == 0 || p % 3 == 0);
                        maxTest = (int)Math.floor((Math.sqrt(p)));
                        di = 2;
                        while (prime[di] <= maxTest) { // test p
                                if (p % prime[di++] == 0) {
                                        negFlag = true;
                                        break;
                                }
                        }
                        if (negFlag == false) flag = true;
                } while (flag == false);
                return p;
        }
}
 樓主| 發表於 2012-9-9 01:45:46 | 顯示全部樓層
這個做法是按照某本書上提示的,包括跳過2與3的倍數以節省執行時間等等。

不過按照目前測試的結果,求一萬個質數也是瞬間就執行完了,可能因為現在電腦的速度實在是太快了。所以或許可以改得簡單點。
 樓主| 發表於 2012-9-9 02:24:29 | 顯示全部樓層
因為想試試求大質數的執行速度,我把程式改寫了一下,讓它只印出所指定的質數,程式如下:

import javax.swing.JOptionPane;

public class SpecificPrimeNumber {

        public static void main(String[] args) {

                String msg = "您想知道第幾個質數?";
                int numPrime = Integer.parseInt(JOptionPane.showInputDialog(msg));
                int[] prime = new int[numPrime];
                prime[0] = 2; prime[1] = 3;
                for (int i = 2; i < numPrime; i++) {
                        prime [i] = nextPrime (i-1, prime);
                }
                msg = "第 "+numPrime+" 號質數 = "+prime[numPrime-1]+".";
                JOptionPane.showMessageDialog(null, msg);
        }

        static int nextPrime(int index, int[] prime) {
                int p = prime[index], di;
                int maxTest;
                boolean flag = false, negFlag; //flag for p, negFlag for di test
                do {  // next p
                        negFlag = false;
                        do p++;
                        while (p % 2 == 0 || p % 3 == 0);
                        maxTest = (int)Math.sqrt(p);
                        di = 0;
                        while (prime[di] <= maxTest) // test p
                                if (p % prime[di++] == 0) {
                                        negFlag = true;
                                        break;
                                }
                        if (negFlag == false) flag = true;
                } while (flag == false);
                return p;
        }
}
頭像被屏蔽
發表於 2012-9-9 02:25:34 | 顯示全部樓層
提示: 作者被禁止或刪除 內容自動屏蔽
 樓主| 發表於 2012-9-9 02:26:44 | 顯示全部樓層
目前測試的結果,求第一千萬個質數的時間還可以接受,結果為179,424,673.

用這個網站: The Number Empire 來測試,結果是正確的 ^^
頭像被屏蔽
發表於 2012-9-9 02:37:40 | 顯示全部樓層
提示: 作者被禁止或刪除 內容自動屏蔽
 樓主| 發表於 2012-9-9 02:44:43 | 顯示全部樓層
書上的意思是,若在測試質數時去掉2和3的倍數,就可以節省許多時間,因為每6個數就有4個符合這個條件:

若n為6的倍數,則n, n+2, n+3, n+4都不可能是質數,因此可以省下三分之二的時間。

我還沒有實測,不過感覺好像差異有限?因為測試是不是2或3的倍數也是要花時間。
頭像被屏蔽
發表於 2012-9-9 02:50:54 | 顯示全部樓層
提示: 作者被禁止或刪除 內容自動屏蔽
頭像被屏蔽
發表於 2012-9-9 03:18:02 | 顯示全部樓層
提示: 作者被禁止或刪除 內容自動屏蔽
 樓主| 發表於 2012-9-9 03:36:08 | 顯示全部樓層
5# ccyvision


0~179,424,673有一千萬個質數
比例未免太高了(1/17.9424673)
您用0~1000去求看看有幾個質數
賓果 發表於 2012-9-9 02:50


質數本來就很不規則喲,以下是第1-170個質數的執行結果,第168個質數997是1000以下最大的。
Prime170.gif
您需要登錄後才可以回帖 登錄 | 註冊 |

本版積分規則



小黑屋|Archiver|手機版|聯成電腦技術論壇  

GMT+8, 2019-10-22 19:57

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回復 返回頂部 返回列表