javascript实现Emrips反质数枚举的示例代码-创新互联-成都创新互联网站建设

关于创新互联

多方位宣传企业产品与服务 突出企业形象

公司简介 公司的服务 荣誉资质 新闻动态 联系我们

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;
}

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


文章名称:javascript实现Emrips反质数枚举的示例代码-创新互联
网页地址:http://kswsj.cn/article/ipeep.html

其他资讯