Emrips 【皇牌天下投注网】反质数枚举 javascript实

来源:http://www.prospettivedarte.com 作者:计算机教程 人气:105 发布时间:2019-05-10
摘要:今天看到一个kata,提出一个“emirps”的概念: 一个质数倒转后得到的是一个不同的质数,这个数叫做“emirps” 。 例如:13,17是质数,31,71也是质数,13和17是“emirps”。但是质数757,78

今天看到一个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:

皇牌天下投注网 1

n=10000000:

皇牌天下投注网 2

本文由皇牌天下投注网发布于计算机教程,转载请注明出处:Emrips 【皇牌天下投注网】反质数枚举 javascript实

关键词:

最火资讯