Emrips 反質數枚舉 javascript實現

今天看到一個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('').reverse().join(''))
    
    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 [
        'n為：' + n,
        '數量為：' + emirpGroup.length,
        '最大數：' + emirpGroup[emirpGroup.length - 1],
        '求和：' + emirpGroup.reduce(function(total,current){
            return total + current;
        })
    ]
}

看一下輸出結果和用時

n=1000000：



n=10000000：