首頁 >web前端 >js教程 >在javascript中如何實作Emrips反質數枚舉

在javascript中如何實作Emrips反質數枚舉

亚连
亚连原創
2018-06-22 14:33:061530瀏覽

下面小編就為大家分享一篇javascript實現Emrips反質數枚舉的範例程式碼,具有很好的參考價值,希望對大家有幫助。一起跟著小編過來看看吧

今天看到一個kata,提出一個「emirps」的概念:一個質數倒轉後得到的是一個不同的質數,這個數叫做「emirps」。

例如:13,17是質數,31,71也是質數,13和17是「emirps」。但是質數757,787,797是回文質數,這意味著反轉的數字與原始數字相同,所以它們不被認為是「emirps」。

題目要求寫一個函數輸入一個正整數n,傳回小於n的「emirps」的數,其中最大「emirps」、以及所有小於n的「emirps」的和。

解題想法為先枚舉所有小於n的質數,然後剔除回文質數以及顛倒後為合數的數。

先寫判斷質數的函數

#主要根據三個數學結論:

#所有合數都是若干個質數的乘積

如一個數可以進行因式分解,那麼兩個因數一定是一個小於等於sqrt(n),一個大於等於sqrt(n )。

所有大於3的質數都是6X 1或6X-1這種形式,也就是6的倍數的相鄰的數,但並不是所有6X 1或6X-1都是質數。

第一個結論用反證法即可證明

第三個結論證明:

我們都把數字都表示為以下形式6X-1、6X、6X 1、6X 2、6X 3、6X 4 (X為正整數) 6X => 2*3x 6X 2 => 2(3x 1) 6X 3 => 3( 2x 1) 6X 4 => 2(3x 2) 可證明這些肯定不為質數,即質數只能為6X-1或者6X-1

代碼:

function isPrimeNumber(num){
  
 if(num == 2 || num == 3){
  return true;
 }/*2、3特殊处理*/
  
 if(num % 6 != 1 && num % 6 != 5){
  return false;
 }/*根据结论三排除*/
  
 for(var i=5;i<=Math.sqrt(num);i+=6){
  if(num % i == 0 || num % (i+2) == 0){
   return false;
  }
 }/*根据结论二、结论三排除*/
  
 return true;
}

再剔除回文質數以及顛倒後為合數的數

function emirpNumber(num){
 
 var reverseNumber = Number(String(num).split(&#39;&#39;).reverse().join(&#39;&#39;))
  
 if(reverseNumber != num && isPrimeNumber(reverseNumber)){
  return true;
 }
 else{
  return false;
 }
}

最後輸出想要的結果

程式碼:

function findEmirp(n){
 
 var emirpGroup = [];
 
 for(var i=1;i<n;i++){
  if(isPrimeNumber(i) && emirpNumber(i)){
   emirpGroup.push(i);   
  }
 }
  
 return [
  &#39;n为:&#39; + n,
  &#39;数量为:&#39; + emirpGroup.length,
  &#39;最大数:&#39; + emirpGroup[emirpGroup.length - 1],
  &#39;求和:&#39; + emirpGroup.reduce(function(total,current){
   return total + current;
  })
 ]
}
看一下輸出結果與使用時

n=1000000:

n=10000000:

############上面是我整理給大家的,希望今後對大家有幫助。 ######相關文章:#########使用Javascript如何實作自訂事件機制############詳細解讀javascript中map資料結構##### #######使用Javascript如何開發二維週視圖日曆############相關JS抽象工廠模式(詳細教學)############在Django與Vue語法中存在衝突問題如何解決######

以上是在javascript中如何實作Emrips反質數枚舉的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn