我正在尝试编写一个程序,它返回最大的回文数,这是两个简单的五位数的乘积,并返回因子本身。
素数是一个自然数,只能除以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>
当我运行这个程序时,它不会在控制台中显示任何内容,我不知道为什么。
看看这个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:你可以把印刷品放到你的功能上以确保他们的进步......
问题::时间复杂性
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
功能没有优化一个。你应该用它。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);
}
}
}