如何优化最大质因数求解脚本以避免大数处理超时？

我尝试解决Project Euler的最大质因数问题，需要找出输入数字的最大质因数。目前用了两种方法，处理常规测试输入都正常，但处理600851475143这类超60亿的大数时会超时，求调整方案。

两种原始实现方法 #

方法一：先判断质数再检查是否为因数 #

function largestPrimeFactor(number) {
  let arr = [];
  for (let i = 2; i <= number; i++) {
    let flag = 0;
    for (let j = 2; j < i; j++) {
      if (i % j === 0) {
        flag = 1;
        break;
      }
    }
    if (flag === 0) {
      if (number % i === 0) {
        arr.push(i);
      }
    }
  }
  return arr[arr.length-1];
}

方法二：先找因数再判断是否为质数 #

function largestPrimeFactor(number) {
  let arr = [];
  for (let i = 2; i <= number; i++) {
    if (number % i === 0) {
      let num = i;
      let tempArr = [];
      for (let j = num-1; j > 1; j--) {
        tempArr.push(num %j );
      }
      if (tempArr.every(val => val > 0)) {
        arr.push(num)
      }
    }
  }
  let largestPrime = arr[arr.length-1]
  return largestPrime;
}

问题分析 #

这两种方法的核心问题是时间复杂度太高：

• 方法一需要遍历到目标数，每个数还要做质数判断，质数判断又要遍历到当前数，时间复杂度为O(n²)，处理大数时完全无法承受。
• 方法二虽然先筛选因数，但因数判断后仍要遍历到因数本身来判断质数，本质时间复杂度和方法一接近，同样不适合大数场景。

优化方案：质因数分解法 #

直接对目标数进行质因数分解，不断用最小的质因数去整除目标数，同时更新目标数，直到无法整除，最后剩下的数就是最大质因数。这种方法的时间复杂度可降到O(√n)，处理大数效率极高。

优化后的代码实现 #

function largestPrimeFactor(number) {
  let largest = 2;
  // 单独处理所有2的因数
  while (number % 2 === 0) {
    largest = 2;
    number = number / 2;
  }
  // 处理奇数因数，从3开始，每次步长为2
  for (let i = 3; i * i <= number; i += 2) {
    // 除尽当前质因数的所有倍数
    while (number % i === 0) {
      largest = i;
      number = number / i;
    }
  }
  // 若剩余数大于2，说明它本身就是质数，即最大质因数
  if (number > 2) {
    largest = number;
  }
  return largest;
}

优化点说明 #

1. 单独处理偶数：2是唯一的偶质数，单独处理后，后续只需遍历奇数，减少一半循环次数。
2. 循环到√number为止：若数n存在大于√n的因数，对应的另一个因数必然小于√n，因此遍历到√n即可，大幅缩减循环范围。
3. 除尽当前因数：找到一个质因数后，不断用它整除目标数直到无法整除，避免后续重复处理该因数的倍数，进一步提升效率。

内容的提问来源于stack exchange，提问作者Xuzmocode