如何在 JavaScript 中找到整数的质因数？

Question

我试图找到一个数字的主要因素，在 javascript 中使用 for 循环在下面记录为“整数”。我似乎无法让它工作，我不确定这是我的 JavaScript 还是我的计算逻辑。

 //integer is the value for which we are finding prime factors
var integer = 13195;

var primeArray = [];

//find divisors starting with 2

for (i = 2; i < integer/2; i++) {
  if (integer % i == 0) {

    //check if divisor is prime
    for (var j = 2; j <= i / 2; j++) {
      if (i % j == 0) {
        isPrime = false;
      } else {
        isPrime = true;
      }
    }

    //if divisor is prime

    if (isPrime == true) {
      //divide integer by prime factor & factor store in array primeArray
      integer /= i
      primeArray.push(i);
    }
  }
}

for (var k = 0; k < primeArray.length; k++) {
  console.log(primeArray[k]);
}

原文由 John the User 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

上面的答案效率低下，复杂度为 O(N^2)。这是 O(N) 复杂度的更好答案。

 function primeFactors(n) {
  const factors = [];
  let divisor = 2;

  while (n >= 2) {
    if (n % divisor == 0) {
      factors.push(divisor);
      n = n / divisor;
    } else {
      divisor++;
    }
  }
  return factors;
}

const randomNumber = Math.floor(Math.random() * 10000);
console.log('Prime factors of', randomNumber + ':', primeFactors(randomNumber).join(' '))

您可以根据需要过滤重复项！

原文由 Alan Judi 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

这是一个有效的解决方案：

 function getPrimeFactors(integer) {
  const primeArray = [];
  let isPrime;

  // Find divisors starting with 2
  for (let i = 2; i <= integer; i++) {
    if (integer % i !== 0) continue;

    // Check if the divisor is a prime number
    for (let j = 2; j <= i / 2; j++) {
      isPrime = i % j !== 0;
    }

    if (!isPrime) continue;
    // if the divisor is prime, divide integer with the number and store it in the array
    integer /= i
    primeArray.push(i);
  }

  return primeArray;
}

console.log(getPrimeFactors(13195).join(', '));

你走在正确的轨道上。有两个小错误。 integer - 1 的评估似乎不正确。我相信更合适的评估是 <= integer 在你的外部 for 循环中。这是因为当您将整数除以 integer /= i 时，最终的整数评估结果为 29 。在这种情况下，最终的质因数也是 29 因此需要评估为 <= 与 < integer - 1

至于为什么最后的日志语句不起作用，有一个简单的拼写错误 primeArray[i] 与 primeArray[k] 。

原文由 War10ck 发布，翻译遵循 CC BY-SA 4.0 许可协议