function isPrime(num){
if(num ==2 || num==3)
return true;
for (var i = 2;i <= n-1;i++) {
if(num % i ==0){
return false;
}
}
return true;
}
方法2:上述判斷方法，明顯存在效率極低的問題。對於每個數n，其實並不需要從2判斷到n-1
我們知道，一個數若可以進行因數分解，那麼分解時得到的兩個數，一定是一個小於等於sqrt(n)和一個大於等於sqrt(n)
據此，上述代碼中並不需要遍歷到n-1，遍歷到sqrt(n)即可，因為若sqrt(n)左側找不到約數，那麼右側也一定找不到約數
12
1×12=12
2×6=12
3×4=12
4×3=12能被2整除的數一定不是素數，所以不用被4、6整除，這樣能減少n/2次執行次數
能被3整除的數一定不是素數，所以不用被6、9整除，這樣能繼續減少執行次數
function isPrime(num){
if(num ==2|| num==3 )
return true;
var temp = parseInt(Math.sqrt(num));
for (var i = 2;i <= temp;i++) {
if(num % i ==0){
return false;
}
}
return true;
}
方法3:function isPrime(num){
if(num ==2 || num==3)
return true;
if(num % 2 == 0 || num % 3 == 0 || num % 5 == 0)
return false;
var temp = parseInt(Math.sqrt(num));
for (var i = 7;i <= temp;i=i+2) {
if(num % i == 0){
return false;
}
}
return true;
}
方法4:證明：令x≥1，將大於等於5的自然數表示如下：
······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1)，6(x+1)+1 ······
可以看到，6的倍數兩側之外的數為6x+2，6x+3，6x+4，由於2(3x+1)，3(2x+1)，2(3x+2)，所以它們一定不是素數，再加上6x本身也不是素數
此時判斷質數可以6個為單元快進，即在循環中i++步長加大為6，加快判斷速度
原因是，假如要判定的數為n，則n必定是6x-1或6x+1的形式，對於循環中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中如果n能被6i，6i+2，6i+4整除，則n至少得是一個偶數，但是6x-1或6x+1的形式明顯是一個奇數，故不成立
另外，如果n能被6i+3整除，則n至少能被3整除，但是6x能被3整除，故6x-1或6x+1(即n)不可能被3整除，故不成立。
綜上，循環中只需要考慮6i-1和6i+1的情況，即循環的步長可以定為6，每次判斷循環變量k和k+2的情況即可，理論上講整體速度應該會是方法(2)的3倍
function isPrime(num){
//兩個較小數
if(num == 2 || num == 3 )
return true ;
//不在6的倍數兩側的一定不是質數
if(num%6 != 1 && num%6 != 5){
return false ;
}
var tmp =Math.sqrt(num);
//在6的倍數兩側的也可能不是質數
for(var i = 5;i <= tmp; i+=6 )
if(num%i == 0 || num%(i+2) == 0)
return false ;
return true;
}