寻找最大的回文数,这是两个简单(素数)五位数的乘积。使用Javascript

问题描述 投票:1回答:2

我正在尝试编写一个程序,它返回最大的回文数,这是两个简单的五位数的乘积,并返回因子本身。

素数是一个自然数,只能除以1和自身(2,3,5,7,11 ......)

回文数字的读取方式相同(例如,ABBA)。

if(isPalin(mul) && isPrime(i) && isPrime(j))

function isPrime(i){
  for (var k = 2; k <= i; k++) {
      if (i%k===0 && i!==k) {
          return false;
    }
  }
return true;
}



<!--code-->


<script>

function largestPalindrome(){

    for(var i = 99999; i>10000; i--){
        for(var j = 99999; j>10000; j--){
            var mul = j*i;
            if(isPalin(mul) && isPrime(i) && isPrime(j)){
                return i * j;


            }
        }

    }
}


function isPalin(i){
    return i.toString() == i.toString().split("").reverse().join("");
    }

function isPrime(i){
  for (var k = 2; k <= i; k++) {
      if (i%k===0 && i!==k) {
          return false;
    }
  }
return true;
}

console.log(largestPalindrome());

</script>

当我运行这个程序时,它不会在控制台中显示任何内容,我不知道为什么。

javascript algorithm
2个回答
1
投票

看看这个link算法的时间复杂度。还有this,看看时间复杂性如何影响你的程序效率。

这部分不是很精确,但可以提供帮助。你的第一个循环运行99999-10000时间。这也适用于第二个循环。在最坏的情况下isPrime运行(99999)。所以if (i%k===0 && i!==k) return false;运行total_ops = (99999-10000)^2*(99999)次(我们跳过你的代码的其他部分)。如果用c ++编写的程序比java脚本更快,它可以运行每秒2*(10^8)简单操作。你的程序运行时间大约(显然超过)total_ops/(2*10^8)(我建议计算它有估计......)。

PS:你可以把印刷品放到你的功能上以确保他们的进步......


0
投票

问题::时间复杂性

improvements

  1. isPrime() function isPrime(n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n%2 == 0 || n%3 == 0) return false; for (var i=5; i*i<=n; i=i+6) if (n%i == 0 || n%(i+2) == 0) return false; return true; } isprime功能没有优化一个。你应该用它。
  2. 找不到每个素数2次。只需找到所有素数一次,将它们存储到一个列表中,然后从主要列表中选择每个数字并检查它是否是回文。 var primelist = []; for(var i = 99999; i > 10000; i++) { if(isprime(i)) { primelist.push(i); } } for (var i = 0; i < primelist.length; i++) { for (var j = 0; j < primelist.length; j++) { if(isPalindrome(i*j)) { // Number you want. return (i*j); } } }
  3. 检查,从最大的素数开始。
  4. 一个5位数字从10000到99999而不是11111到99999开始。虽然,它不会改变函数的输出。
© www.soinside.com 2019 - 2024. All rights reserved.