javascript - 欧拉计划 #29 : Why is my answer off by 37?

Question

我正在研究 Problem 29 :

How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

我用过滤器做了一个暴力解决方案:

var main = function() {

    var arr = [];

    for (var a = 2; a <= 100; a++) {
        for (var b = 2; b <= 100; b++) {
            arr.push(BigInt(Math.pow(a, b)));
        }
    }
    //arr.sort((a, b) => a - b);

    return arr.filter(function(elem, pos) {
        return arr.indexOf(elem) == pos;
    }).length;
}

console.log(main());

我的程序运行良好。虽然我得到的结果是 9220，但正确答案是 9183。我在这里缺少什么？

Answer 1

问题是

BigInt(Math.pow(a, b))

即使使用 BigInt，表达式 inside 在传递给 BigInt 之前也会先求值，而 Javascript 无法精确处理巨大的数字。该行为看起来取决于浏览器，不幸的是，该问题在每个环境中都无法充分重现。

对于跨浏览器的解决方案，您必须找到另一种方法，例如找到每个数字的不同因子，并过滤掉具有重复因子计数的数字。 (例如，2^4 的质因数是 2x2x2x2，与 4^2 相同 - 过滤掉所有此类重复项。)

例如:

const isPrime = num => {
  for(let i = 2; i < num; i++)
    if(num % i === 0) return false;
  return num > 1;
}
const primes = Array.from(
  { length: 100 },
  (_, i) => i + 1
).filter(isPrime);

const addPrimesToObj = (num, prime, obj) => {
  while ((num / prime) % 1 === 0) {
    obj[prime] = (obj[prime] || 0) + 1;
    num = num / prime;
  }
  return num;
};
var main = function() {
  const factorsSet = new Set();
  for (let a = 2; a <= 100; a++) {
    for (let b = 2; b <= 100; b++) {
      const theseFactors = {};
      for (let i = 0; i < b; i++) {
        let innerA = a;
        primes.forEach((prime) => {
          innerA = addPrimesToObj(innerA, prime, theseFactors);
        });
      }
      const factorsStr = Object.entries(theseFactors)
        .map(([key, val]) => `${key}-${val}`)
        .join('_');
      factorsSet.add(factorsStr);
    }
  }
  return factorsSet.size;
}

console.log(main());