如何做出一個判斷質數的程式?

質數是指數值在1以上,而且該數值的因數只有本身跟1。

我有拉了前面...但是判斷質數我該怎設定??

以下是我自己拉的前面...但是要怎判斷1以後的質數我就不知道該怎設定了@@

![](upload://hbUh2oOMxPjTjWnGcsOZFbBi8nn.jpeg)

![](upload://wJ5xVOOUz0ZxDH2alVq5dXuhev.jpeg)

triple017339232.59125

對於質數的說明,請參考:http://zh.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

裡面有提到如何判斷質數:

[Quote]

尋找質數

尋找在給定限度內的質數排列,埃拉托斯特尼篩法法是個很好的方法。然而在實際中,我們往往是想知道一個給定數是否是質數,而不是生成一個質數排列。進而,知道答案是很高的機率就是已經很滿意的了,用素性測試迅速地檢查一個給定數(例如,有幾千位數的長度)是否是質數是可能的。典型的方法是隨機選取一個數,然後圍繞著這個數和可能的質數N檢查一些方程式。重複這個過程幾次後,它宣佈這個數是明顯的合數或者可能是質數。這種方法是不完美的:對某些測試而言,例如費馬測試,不論選取了多少隨機數都有可能將一些合數判斷成可能的質數,這就引出了另一種數偽質數。而像米勒-拉賓測試,雖然只要選取夠多數字來檢驗方程式,就可以保證其檢驗出的質數性是正確的,但這個保證門檻的數量太過龐大,甚至比試除法所需的還要多,在有限時間內運行起來只能知道答案正確的機率很高,不能保證一定正確。

目前最大的已知質數是230402457 − 1(此數字位長度是9,152,052),它是在2005年12月15日GIMPS發現。這組織也在2005年2月18日發現了目前所知第二大的已知質數225964951 - 1(此數字位長度是7,816,230)。

數學家一直努力找尋產生質數的公式,但截至目前為止,並沒有一個基本函數或是多項式可以正確產生所有的質數。歷史上有許多試驗的例子:17世紀法國數學家梅森(Mersenne)在他的一個著作當中討論了這樣一種我們現在稱之為梅森質數的質數,Mp=2p - 1,本來以為只要p是一個質數,n = 2p - 1就會是一個質數,這在p = 3p = 5p = 7都是正確的,但是p = 11}-就不是質數了。

檢驗質數

檢查一個正整數N是否為質數,最簡單的方法就是試除法,將該數N用小於等於的所有質數去試除,若均無法整除,則N為質數。

2002年,印度人 M. Agrawal 、N. Kayal 以及 N. Saxena 提出了 AKS 質數檢驗演算法,證明了可以在多項式時間內檢驗是否為質數。

[/QUOTE]

依照上述的辦法,寫一個LabVIEW程式來判斷是否為質數應該不難。

在NI網站也有一些範例程式,張貼出來您參考一下:

網站連結:Generating Prime Numbers
程式:primegen.llb

NI網站的範例程式是找出小於輸入數值的所有質數,沒有判斷輸入的數值是否為質數的功能。

我是想到一種較笨的方法來判定輸入的數值是否為質數,不過和NI網站的範例程式有一樣的毛病,只要輸入數值超過7位數以上就要等一段時間才有結果,建議輸入的數值不要超過8位數。有高手知道如何有效率判斷9位數以上數值是否為質數的方法嗎?

![](upload://uqajs6Waq0xDzs2GuoexUpTdO20.jpeg)

質數判斷.vi

[QUOTE=liuyunan]

NI網站的範例程式是找出小於輸入數值的所有質數,沒有判斷輸入的數值是否為質數的功能。

我是想到一種較笨的方法來判定輸入的數值是否為質數,不過和NI網站的範例程式有一樣的毛病,只要輸入數值超過7位數以上就要等一段時間才有結果,建議輸入的數值不要超過8位數。有高手知道如何有效率判斷9位數以上數值是否為質數的方法嗎?

![](upload://uqajs6Waq0xDzs2GuoexUpTdO20.jpeg)

質數判斷.vi

[/QUOTE]
因為你的程式中做了很多虛功。二樓的回答已經很清楚了。
要判斷一個數(假設為X)是否為質數,只需要測試(根號X)以下的所有質數即可。
並不需要從3開始一個一個測試到X-1為止。
比如說,你要測試101是否為質數,根號101為10點多,在此之下的質數只有2、3、5、7
因此你只要拿這四個數字下去和101相除即可。
問題是,怎麼找出(根號X)之下所有質數?
同樣參考二樓的回答,使用埃拉托斯特尼篩法」來篩選出所有質數在進行計算即可。

這樣做下來,就算是12位的數字都可以很快找出答案。但相對的,程式上寫起來就會相對複雜許多。

[QUOTE=Bridge]
因為你的程式中做了很多虛功。二樓的回答已經很清楚了。
要判斷一個數(假設為X)是否為質數,只需要測試(根號X)以下的所有質數即可。
並不需要從3開始一個一個測試到X-1為止。
比如說,你要測試101是否為質數,根號101為10點多,在此之下的質數只有2、3、5、7
因此你只要拿這四個數字下去和101相除即可。
問題是,怎麼找出(根號X)之下所有質數?
同樣參考二樓的回答,使用埃拉托斯特尼篩法」來篩選出所有質數在進行計算即可。

這樣做下來,就算是12位的數字都可以很快找出答案。但相對的,程式上寫起來就會相對複雜許多。
[/QUOTE]

基本上NI的範例也算是用埃拉托斯特尼篩法」來篩選出所有質數,我之前有先寫過把那個範例當SubVI來用,在輸入數值到12位以上時一樣要等很久。

NI的那個範例也是有不少虛功動作,而我有在之前PO的那個程式在輸入數值後面加個開根號的VI,做出來的速度經測試,只比以下的程式略慢一些。

![](upload://iwbhaNYfThPzNHjBCQZXxvpqTt7.jpeg)

![](upload://spyHt2a1MxeEZ6QXhbEKk5NuKxU.jpeg)

質數判斷.llb

補充一下

如果只是問比輸入數值小的質數有多少個時?用NI的那個範例找起來還蠻快的。

但用找出來的質數陣列去除求出輸入數值是否為質數也不容易,就算輸入的12位數都是1,找出的質數也有幾萬個,要算幾萬次才有結果。


PrimeFinding.rar

奇怪,難道是CPU有差嗎?我執行我寫的程式還蠻快的耶。
12位數的數字不用一秒就可以算出來了呀。
到13或14位才會稍微慢一點。

12位數的數字不用一秒?用我的電腦執行你程式的結果…看來我該考慮買新電腦了

[QUOTE=liuyunan]12位數的數字不用一秒?用我的電腦執行你程式的結果…看來我該考慮買新電腦了[/QUOTE]

啊!!拍水,我的錯

我的電腦是p4 3.0G + 1000 DDR Ram
我一直以為自己的電腦效能並沒有多好。
不過看來造成時間上的差異應該是來自電腦硬體的關係了

我寫了一個計算質數的小程式,有興趣的網友可以看看:

程式:求質數.vi


http://tw.myblog.yahoo.com/liu-yunan/article?mid=609&prev=673&next=387&l=f&fid=15