找到最简单的基础及其指数给定的产品

Question

给定一个乘积，我想找到最简化的底数及其对应的指数。例如，乘积 343 的底数为 7，指数为 3。如果某个乘积 return 有多组底数和指数，则只考虑最简单的底数。例如，64 的乘积将 return 以 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 }

从素数列表开始并遍历它而不是遍历所有奇数会有所帮助，如果您所处的约束条件允许的话。

Answer 2

我没有看到更好的逻辑，但是我可以想到一些优化：

你应该让 i 从 2 到 Math.max(2, Math.floor(Math.sqrt(product)))

不是来自 1 因为 Math.pow(1, <something>) 总是等于 1

没有正整数 N = Math.pow(a, b) 其中 a 和 b 是大于 1 且 b > sqrt(N)

的正整数

Answer 3

此代码检查一个数字是否是产品的 base，而不是产品的 factor。你看，对于像 42 这样的乘积，没有匹配它的底数和指数，但是会有可整除的整数 - 比如 2、6、7 和 21。我们不关心这些因素中的任何一个是一个整数，而是一个评估为整数的基数。

var isRoot = function (n, root) { return Number.isInteger(getBase(n, root)); };
const getBase = (n, root) => parseFloat(Math.pow(n, 1 / root).toFixed(3));
const findExponent = (product, exponent) => ({
    base: getBase(product, exponent),
    exponent
});
function findBaseAndExponent(product) {
    for (var i = Math.ceil(Math.sqrt(product)); i >= 2; i--) {
        if (isRoot(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(42)); // Output: { base: null, exponent: null }

找到最简单的基础及其指数给定的产品

Find simplest base and its exponent given product

javascript

logarithm