判斷質數的演算法

Ⅰ 任意給定一個正整數n，設計出判斷n是否為質數的一個演算法

首先，基本的方法就是用這個數除以小於它的所有質數看余數
但n太大的話，這需要很大的質數表
因此n太大的情況下，基本都是用分布式運算找質數的
即每個數讓終端上的一個人去驗證，有結果了再提交上來
通常編程，所輸入的質數不能太大

Ⅱ 判斷一個數是否是質數

判斷一個數是否是質數
最暴力的解法
利用質數的性質：設i為質數，則i只能被 1 和 i整除。
因此對於i，我們可以令 2..i-1 依次除以i，如果均不能被整除，則說明是質數。
代碼如下
private static boolean isPrime1(int nr) {
for (int i = 2; i < nr; i++) {
if (nr % i == 0) return false;
}
return true;
}123456123456

稍微暴力的方法
同樣利用其性質，但我們可以注意到，當 x > i / 2 時，則 x 肯定不能被 i 整除。
對於i，我們可以令 2..x 依次除以i，其中x為sqrt(i)
代碼如下
private static boolean isPrime2(int nr) {
for (int i = 2; i*i <= nr; i++) {
if (nr % i == 0) return false;
}
return true;
}123456123456

效率更高的演算法
提供一個數組 nums = {2, 3, 4, 5,... 17}
我們知道 nums[0] 為質數，將nums中所有能被nums[0]整除的數移除，此時數組為 nus = {2, 3, 5, 7, 9, 11, 13, 15, 17}
接著將所有能被 3 整除的數移除。此時為 nums = {2, 3, 5, 7, 11, 13, 17}
接下來的數是 5，因為 5*5 > 17，所以移除過程結束。此時的nums值為輸入nums中的所有素數。
上面的步驟之所以正確是因為：合數必定可以由質數相乘得到，則對任意質數i，如果其不能被sqrt(i)前的所有質數整除，則其必定為質數（小於 sqrt(i) 的合數必定可以被小於 sqrt(i) 的質數合成）。
代碼如下
private static void primeList(List<Integer> nums) {
for (int i = 0; i < nums.size(); i++) {
if (nums.get(i)*nums.get(i) <= nums.get(nums.size()-1)) {
for (int j = i+1; j < nums.size(); j++) {
if (nums.get(j) % nums.get(i) == 0) nums.remove(j);
}
} else {
return ;
}
}
}12345678910111234567891011

此演算法存在的問題也很明顯，說它是判斷一個數是否是質數獲取不太准確，其作用應該是 「列印出小於等於某值的所有質數」
使用素數表
上面的演算法有一個缺陷，它對輸入數組要求較高，要求包含了數組最大值之前的所有素數，且是已排序的。也就是說它不能用來直接判斷一個數是否是素數。
通常情況下，我們會使用一個素數表。接著用來整除的元素便可以從這個素數表中獲取
這種演算法的局限在於素數表是有限的，對於超出素數表最大值平方的數則需要加上上述方法二的步驟才能判斷（盡管這種情況不多）。
演算法實現同上，只是此時直接從素數表獲取素數即可
http://blog.csdn.net/lingeors/article/details/56288375?locationNum=13&fps=1

Ⅲ 任意給定一個正整數n，設計出判斷n是否為質數的一個演算法．

（1）當n=1時，n既不是質數，也不是合數；
（2）當n=2時，n是質數；
（3）當n≥3時，從2到n-1依次判斷是否存在n的因數（因數1除外），若存在，則n是合數；若不存在，則n是質數．

Ⅳ 設計一個演算法判斷一個數是不是質數

演算法分析：（1）根據質數的定義，可以這樣判斷：依次用2—6除7，如果它們中有一個能整除7，則7不是質數，否則7是質數.
演算法如下：（1）第一步，用2除7，得到余數1.因為余數不為0，所以2不能整除7.
第二步，用3除7，得到余數1.因為余數不為0，所以3不能整除7.
第三步，用4除7，得到余數3.因為余數不為0，所以4不能整除7.
第四步，用5除7，得到余數2.因為余數不為0，所以5不能整除7.
第五步，用6除7，得到余數1.因為余數不為0，所以6不能整除7.因此，7是質數.
（2）類似地，可寫出「判斷35是否為質數」的演算法：第一步，用2除35，得到余數1.因為余數不為0，所以2不能整除35.
第二步，用3除35，得到余數2.因為余數不為0，所以3不能整除35.
第三步，用4除35，得到余數3.因為余數不為0，所以4不能整除35.
第四步，用5除35，得到余數0.因為余數為0，所以5能整除35.因此，35不是質數.
點評：上述演算法有很大的局限性，用上述演算法判斷35是否為質數還可以，如果判斷1997是否為質數就麻煩了，因此，我們需要尋找普適性的演算法步驟.

Ⅳ 求質數方法

篩法求質數：

用篩法求質數的基本思想是：把從1開始的、某一范圍內的正整數從小到大順序排列， 1不是質數，首先把它篩掉。剩下的數中選擇最小的數是質數，然後去掉它的倍數。依次類推，直到篩子為空時結束。如有：

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

1不是質數，去掉。剩下的數中2最小，是質數，去掉2的倍數，餘下的數是：

3 5 7 9 11 13 15 17 19 21 23 25 27 29

剩下的數中3最小，是質數，去掉3的倍數，如此下去直到所有的數都被篩完，求出的質數為：

2 3 5 7 11 13 17 19 23 29

(5)判斷質數的演算法擴展閱讀：

質數被利用在密碼學上，所謂的公鑰就是將想要傳遞的信息在編碼時加入質數，編碼之後傳送給收信人，任何人收到此信息後，若沒有此收信人所擁有的密鑰，則解密的過程中，將會因為找質數的過程過久，使即使取得信息也會無意義。

在汽車變速箱齒輪的設計上，相鄰的兩個大小齒輪齒數設計成質數，以增加兩齒輪內兩個相同的齒相遇嚙合次數的最小公倍數，可增強耐用度減少故障。。

參考資料：

網路--篩法求素數

Ⅵ python求質數的演算法

很早 的一個 函數

Ⅶ 請寫出判斷n(n＞2)是否為質數的演算法.

演算法如下： 第一步，給定大於2的整數n. 第二步，令i=2. 第三步，用i除n,得到余數r. 第四步，判斷「r=0」是否成立.若是，則n不是質數，結束演算法；否則，將i的值增加1，仍用i表示. 第五步，判斷「i＞（n-1）」是否成立.若是，則n是質數，結束演算法；否則，返回第三步. 分析：對於任意的整數n(n＞2)，若用i表示2—(n-1)中的任意整數，則「判斷n是否為質數」的演算法包含下面的重復操作：用i除n,得到余數r.判斷余數r是否為0，若是，則不是質數；否則，將i的值增加1，再執行同樣的操作. 這個操作一直要進行到i的值等於(n-1)為止.

Ⅷ 如何求一個數組中的數是否為質數

根據質數的定義，在判斷一個數n是否是質數時，只要用1至n-1去除n，看看能否整除即可。
還有更好的辦法：先找一個數m，使m的平方大於n，再用小於等於m的質數去除n（n為被除數），如果都不能整除，則n必然是質數。如我們要判斷1993是不是質數，50*50>1993，那麼只要用1993除以<50的質數看是否能整除，若不能即為質數。100以內的質數有25個，還是比較好記的，只要記熟100以內質數，就可以快速判斷10000以內的數是不是質數。
100以內的質數有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97，在100內共有25個質數。

只有1和它本身兩個因數的自然數，叫質數（或稱素數）。（如：由2÷1=2，2÷2=1，可知2的因數只有1和它本身2這兩個約數，所以2就是質數。與之相對立的是合數：「除了1和它本身兩個因數外，還有其它因數的數，叫合數。」如：4÷1=4，4÷2=2，4÷4=1，很顯然，4的因數除了1和它本身4這兩個因數以外，還有因數2，所以4是合數。）

Ⅸ 尋找質數的演算法

沒有什麼好的辦法,如果用程序,就計算n除以2到根號n最接近的整數,如果都不能整除,n就是質數
比如101,要計算19除以2,3,4,5直到10,如果都不能整除,就是質數.
如果你要手動計算,就挨個寫,2,3,5,7,11,13,如果數字足夠大,不需要像程序一樣挨個除,只需要除以比它小的質數就可以了.

Ⅹ 判斷一個數是否為素數的演算法

找質數的方法：寫出這個數的因數。再判斷這個數是質數還是合數。
1、一個數除了1和本身，不再有別的約數，這樣的數叫做質數或者素數。例如：2，3，5，7，11，13，17，19，23，29等等。
2、一個數，除了1和本身，還的別的因數，這樣的數叫做合數。例如4、8、8、9等等。例如：2的所有因數是1和2兩個，所以2是質數。例如6的所有因數是：1，2，3，6。一共是4個，所以6是合數。
找因12的因數：
1×12=12
2×6=12
3×4=12
所以12的因數有：1，2，3，4，6，12。共6個。
找因數的方法可以把這個數分成兩個因數相乘的積。從一開始比較容易找，寫的時候最好能從小到大寫出來。重復的只能寫一個。例如9的因數：1×9=9
3×3=9
9的因數是：1，3，9共3個。（重復的3隻能寫一個。）