求素?cái)?shù)的方法：1、遍歷1~n區(qū)間中的所有自然數(shù)給n來(lái)除，若余數(shù)為0則表示該數(shù)n不是素?cái)?shù)，否則就是素?cái)?shù)，語(yǔ)法“for(i=2;i<n;i++){if(n%i===0){return false;}}”。2、利用素?cái)?shù)平方根范圍，語(yǔ)法“for(i=2;i<=Math.sqrt(n);i++){if(n%i===0){return false;}}”。

前端（vue）入門到精通課程：進(jìn)入學(xué)習(xí)

本教程操作環(huán)境：windows7系統(tǒng)、javascript1.8.5版、Dell G3電腦。

素?cái)?shù)的概念

素?cái)?shù)又叫質(zhì)數(shù)，素?cái)?shù)是指在大于1的自然數(shù)中，除了1和它本身以外，不能被其他自然數(shù)整除的數(shù)。

100以內(nèi)的素?cái)?shù)：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，共計(jì)25個(gè)。

JavaScript判定素?cái)?shù)的四種方法

1、素?cái)?shù)只能被1和自身整除

素?cái)?shù)只能被1和自身整除，所以遍歷（1，n）開區(qū)間中的所有自然數(shù)給n來(lái)除，若存在整除，即余數(shù)為0，則表示該數(shù)n不是素?cái)?shù)，否則就是素?cái)?shù)。

function isPrime(n) {   n = parseInt(n);     if (n <= 3) {     return n > 1;   }     for (let i = 2; i < n; i++) {     if (n % i === 0) {       return false;     }   }   return true; }

但是這種算法的復(fù)雜度為O(n)

2、素?cái)?shù)平方根范圍

假設(shè)n不是素?cái)?shù)，則n除了可以被1和n整除外，還可以被i、j整除，即 n / i = j…0，比如15不是素?cái)?shù)，15 / 3 = 5，比如35不是素?cái)?shù)，35 / 5 = 7，此時(shí)i,j必然分別處于(1, Math.sqrt(n)]和[Math.sqrt(n), n） 之中，比如Math.sqrt(15) ≈ 3.8，則 3處于（1，3.8]，5處于[3.8, 15）。比如Math.sqrt(4) = 2，則2處于(1,2]中，也處于[2,4)中。

function isPrime(n) {   n = parseInt(n);     if (n <= 3) {     return n > 1;   }     for (let i = 2; i <= Math.sqrt(n); i++) {     if (n % i === 0) {       return false;     }   }   return true; }

此時(shí)算法復(fù)雜度為O（sqrt(n)）

3、素?cái)?shù)不能非2的其他偶數(shù)

除了2，所有偶數(shù)都不是素?cái)?shù)

function isPrime(n) {   n = parseInt(n);     if (n <= 3) {     return n > 1;   }     if (n % 2 === 0) {     return false;   }     for (let i = 3; i <= Math.sqrt(n); i += 2) {     if (n % i === 0) {       return false;     }   }   return true; }

for循環(huán)中n，只能為上圖淺藍(lán)色部分。

因此上面算法減少了一半的循環(huán)，時(shí)間復(fù)雜度為O（sqrt(n) / 2）

需要注意的是，本算法的代碼不能將n % 2 === 0 的判斷條件加入到循環(huán)中，如下代碼存在漏洞

function isPrime(n) {   n = parseInt(n);     if (n <= 3) {     return n > 1;   }     for (let i = 3; i <= Math.sqrt(n); i += 2) {     if (n % 2 === 0 || n % i === 0) {       return false;     }   }   return true; }

此時(shí)4、6、8都會(huì)被判定為素?cái)?shù)。

漏洞形成的原因是，for循環(huán)的循環(huán)條件 i <= Math.sqrt(n) 不成立，比如n=4時(shí)，i <= Math.sqrt(4) 不成立，導(dǎo)致n無(wú)法進(jìn)入循環(huán)中n % 2 === 0 的判斷，而是直接退出循環(huán)，return true。

該算法只能保證循環(huán)條件 i <= Math.sqrt(n) 成立的n值判斷素?cái)?shù)正確，即 n >= i^2 = 9 時(shí)。

4、大于等于5的素?cái)?shù)一定和6的倍數(shù)相鄰

大于等于5的素?cái)?shù)一定和6的倍數(shù)相鄰

（注意這句話不等價(jià)于：和6的倍數(shù)相鄰的數(shù)一定是大于5的素?cái)?shù)，該結(jié)論不成立。）

如上圖中，將大于等于5的數(shù)分為了：6y-1、6y、6y+1、6y+2、6y+3、6y+4（y>=1）

其中，6y、6y+2、6y+3、6y+4都不可能是素?cái)?shù)，只有6y-1和6y+1可能是素?cái)?shù)。

另外，6y-1（y>=1）和 6y + 5 （y>=0）等價(jià)。

所以，我們可以將n不為6y-1（或6y+5）和6y+1的數(shù)直接排除，排除方法為，

  if (n % 6 !== 1 && n % 6 !== 5) {     return false;   }

下面要剔除掉6y-1（或6y+5）和6y+1中的非素?cái)?shù)，

  for (let i = 5; i <= Math.sqrt(n); i += 6) {     if (n % i === 0 || n % (i + 2) === 0) {       return false;     }   }

這里大家比較疑惑的可能有兩點(diǎn)：

• for循環(huán)i自增為啥是 6
• for循環(huán)中素?cái)?shù)判定的條件為啥是 n % i === 0 || n % (i+2) === 0

我們看上面圖解，可以發(fā)現(xiàn)，6y-1，是基數(shù)為5，差值為6的等差數(shù)列，即 5 + 6x :

• 對(duì)于 5 + 6x 而言，如果x為5的倍數(shù)（5 * z），則5 + 6x = 5 + 6 * 5 * z = 5 *（1+6z）,則此時(shí)5 + 6x可以被5整除。
• 5 + 6x 還可以轉(zhuǎn)化為 5 + 6 + 6 * (x-1) = 11 + 6(x-1)，則只要x-1為11的倍數(shù)，則5 + 6x可以被11整除，
• 5 + 6x 還可以轉(zhuǎn)化為 5 + 12 + 6 * (x-2) = 17 + 6(x-2)，則只要x-2為17的倍數(shù)，則5 + 6x可以被17整除
• ……

6y+1，是基數(shù)為7，差值為6的等差數(shù)列，即 7 + 6x :

• 對(duì)于 7 + 6x 而言，如果x為7的倍數(shù)（7 * z），則7 + 6x = 7 + 6 * 7 * z = 7 *（1+6z）,則此時(shí)7 + 6x可以被7整除。
• 7 + 6x 還可以轉(zhuǎn)化為 7 + 6 + 6 * (x-1) = 13 + 6(x-1)，則只要x-1為13的倍數(shù)，則7 + 6x可以被13整除，
• 7 + 6x 還可以轉(zhuǎn)化為 7 + 12 + 6 * (x-2) = 19 + 6(x-2)，則只要x-2為19的倍數(shù)，則7 + 6x可以被19整除，
• ……

所以6y-1和6y+1可能整除的數(shù)自增量為6，這是for循環(huán)i自增為啥是 6的原因

且6y-1和6y+1的整除數(shù)基數(shù)為5和7，相差為2，這是for循環(huán)中素?cái)?shù)判定的條件為啥是 n % i === 0 || n % (i+2) === 0的原因

function isPrime(n) {   n = parseInt(n);     if (n <= 3) {     return n > 1;   }     if (n % 6 !== 1 && n % 6 !== 5) {     return false;   }     for (let i = 5; i <= Math.sqrt(n); i += 6) {     if (n % i === 0 || n % (i + 2) === 0) {       return false;     }   }     return true; }

此時(shí)時(shí)間復(fù)雜度為 O（sqrt(n) / 3）

【