javascript - 给定乘积，找到最简单的底数及其指数

Question

给定一个乘积，我想找到最简化的底数及其相应的指数。例如，343 的乘积将产生底数为 7 且指数为 3。如果某个乘积返回多组底数和指数，则仅考虑最简单的底数。例如，64 的乘积将返回基数 2 和指数 6，并消除基数 4 和指数 3、基数 8 和指数 2 的较高组合。

现在，我已经编写了一个适用于这种情况的程序。然而，它似乎相对不正统，并且可能需要很长时间才能编译指定的 product 参数的给定高数字。是否有更好、更有效的方法来编写函数，可能使用对数？我似乎找不到任何关于此类编程问题的信息。

function findBaseAndExponent(product) {
   product = Math.round(product);
   var base = 0;
   var exp = 0;
   var abort = false;
   for (var i = 1; i <= product && !abort; i++) {
       for (var j = 1; j <= product && !abort; j++) {
          const currProd = Math.pow(i, j);
          if (currProd == product) {
             base = i;
             exp = j;
             abort = true;
          }
          if (currProd > product){
             break;
          }
      }
   }
   if (base == product && exp == 1) {
      base = "N/A";
      exp = "N/A";
   }
   return { "base": base, "exponent": exp };
}

console.log(findBaseAndExponent(343)); // Output: { base: 7, exponent: 3 }
console.log(findBaseAndExponent(64)); // Output: { base: 2, exponent: 6 }
console.log(findBaseAndExponent(41)); // Output: { base: N/A, exponent: N/A }

Answer 1

问题看起来简化为找到第一个除以乘积的数字(从尽可能小的第一个数字开始)，然后找到它除以多少次。

比你的方法更简单、更有效的方法是从 2 开始，然后检查 3，然后为后续每次迭代增加 2，直到达到乘积的平方根。它不是最效率最高的，但它更好并且更容易实现。

const isDivisible = (a, b) => Number.isInteger(a / b);
const log = (n, base) => Math.log(n) / Math.log(base);
const findExponent = (product, base) => ({
  base,
  exponent: Math.round(log(product, base))
});
function findBaseAndExponent(product) {
  if (isDivisible(product, 2)) return findExponent(product, 2);
  for (let i = 3, limit = Math.floor(Math.sqrt(product)); i <= limit; i += 2) {
    if (isDivisible(product, i)) return findExponent(product, i);
  }
  return { base: null, exponent: null };
}

console.log(findBaseAndExponent(343)); // Output: { base: 7, exponent: 3 }
console.log(findBaseAndExponent(64)); // Output: { base: 2, exponent: 6 }
console.log(findBaseAndExponent(41)); // Output: { base: N/A, exponent: N/A }

从素数列表开始并对其进行迭代而不是迭代所有奇数会有所帮助，如果您所受到的约束允许的话。