源码网商城,靠谱的源码在线交易网站 我的订单 购物车 帮助

源码网商城

javascript实现Emrips反质数枚举的示例代码

  • 时间:2020-01-12 19:30 编辑: 来源: 阅读:
  • 扫一扫,手机访问
摘要:javascript实现Emrips反质数枚举的示例代码
今天看到一个kata,提出一个“emirps”的概念:一个质数倒转后得到的是一个不同的质数,这个数叫做“emirps”。 例如:13,17是质数,31,71也是质数,13和17是“emirps”。 但是质数757,787,797是回文质数,这意味着反转的数字与原始数字相同,所以它们不被认为是“emirps”。 题目要求写一个函数输入一个正整数n,返回小于n的“emirps”的个数,其中最大“emirps”、以及所有小于n的“emirps”的和。 解题思路为先枚举出所有小于n的质数,然后剔除回文质数以及颠倒后为合数的数。 [b]先写判断质数的函数[/b] [b]主要根据三个数学结论:[/b] 所有合数都是若干个质数的乘积 如一个数可以进行因式分解,那么两个因数一定是一个小于等于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 [b]代码:[/b]
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;
}
再剔除回文质数以及颠倒后为合数的数 [b]代码:[/b]
function emirpNumber(num){
 
 var reverseNumber = Number(String(num).split('').reverse().join(''))
  
 if(reverseNumber != num && isPrimeNumber(reverseNumber)){
  return true;
 }
 else{
  return false;
 }
}
最后输出想要的结果 [b]代码:[/b]
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;
  })
 ]
}
[b]看一下输出结果和用时[/b] [b]n=1000000:[/b] [img]http://files.jb51.net/file_images/article/201712/2017120616172185.jpg[/img] [b]n=10000000:[/b] [img]http://files.jb51.net/file_images/article/201712/2017120616172186.jpg[/img] 以上这篇javascript实现Emrips反质数枚举的示例代码就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持编程素材网。
  • 全部评论(0)
联系客服
客服电话:
400-000-3129
微信版

扫一扫进微信版
返回顶部