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('').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：

以上这篇javascript实现emrips反质数枚举的示例代码就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。