一、概念介紹
? ? 大家中學(xué)都學(xué)過(guò)杖刷，就不過(guò)多介紹了励饵，大致提兩點(diǎn)：
質(zhì)數(shù)又稱(chēng)素?cái)?shù)。一個(gè)大于1的自然數(shù)滑燃，除了1和它自身外役听，不能被其他自然數(shù)整除的數(shù)叫做質(zhì)數(shù)；否則稱(chēng)為合數(shù)表窘。
0和1既不是質(zhì)數(shù)也不是合數(shù)典予，最小的質(zhì)數(shù)是2
二、方法介紹
1.最直觀(guān)乐严，但效率最低的寫(xiě)法
public static boolean isPrime(int n){
if (n <= 3) {
return n > 1;
}
for(int i = 2; i < n; i++){
if (n % i == 0) {
return false;
}
}
return true;
}
這里特殊處理了一下小于等于3的數(shù)瘤袖，因?yàn)樾∮诘扔?的自然數(shù)只有2和3是質(zhì)數(shù)。
? ? 然后昂验，我們只需要從2開(kāi)始捂敌，一直到小于其自身，依次判斷能否被n整除即可既琴，能夠整除則不是質(zhì)數(shù)占婉，否則是質(zhì)數(shù)。
2.初步優(yōu)化
? ? 假如n是合數(shù)甫恩，必然存在非1的兩個(gè)約數(shù)p1和p2逆济，其中p1<=sqrt(n)，p2>=sqrt(n)。由此我們可以改進(jìn)上述方法優(yōu)化循環(huán)次數(shù)奖慌。如下：
public static boolean isPrime(int n) {
if (n <= 3) {
return n > 1;
}
int sqrt = (int)Math.sqrt(n);
for (int i = 2; i <= sqrt; i++) {
if(n % i == 0) {
return false;
}
}
return true;
}
3.繼續(xù)優(yōu)化
? ? 我們繼續(xù)分析霎终，其實(shí)質(zhì)數(shù)還有一個(gè)特點(diǎn)，就是它總是等于 6x-1 或者 6x+1升薯，其中 x 是大于等于1的自然數(shù)莱褒。
? ? 如何論證這個(gè)結(jié)論呢，其實(shí)不難涎劈。首先 6x 肯定不是質(zhì)數(shù)广凸，因?yàn)樗鼙?6 整除；其次 6x+2 肯定也不是質(zhì)數(shù)蛛枚，因?yàn)樗€能被2整除谅海；依次類(lèi)推，6x+3 肯定能被 3 整除蹦浦；6x+4 肯定能被 2 整除扭吁。那么，就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是質(zhì)數(shù)了盲镶。所以循環(huán)的步長(zhǎng)可以設(shè)為 6侥袜，然后每次只判斷 6 兩側(cè)的數(shù)即可。
public static boolean isPrime(int num) {
if (num <= 3) {
return num > 1;
}
// 不在6的倍數(shù)兩側(cè)的一定不是質(zhì)數(shù)
if (num % 6 != 1 && num % 6 != 5) {
return false;
}
int sqrt = (int) Math.sqrt(num);
for (int i = 5; i <= sqrt; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
對(duì)于輸入的自然數(shù) n 較小時(shí)溉贿，也許效果不怎么明顯枫吧，但是當(dāng) n 越來(lái)越大后，該方法的執(zhí)行效率就會(huì)越來(lái)越明顯了宇色。
