javascript - 最大质因数

Question

我正在尝试完成 algorithm challenge to find the largest prime factor of 600851475143 .我不一定要答案。只是想弄清楚为什么这段代码不起作用。为什么它返回“未定义”而不是数字？

let isPrime = n => {
    let div = n - 1;
    while (div > 1) {
        if (n % div == 0) return false;
        div--;
    }
    return true;
};

let primeFactor = x => {
    for (let i = Math.floor(x / 2); i > 1; i--) {
        if (x % i == 0 && isPrime(i) == true) {
            return i;
        }
    }
};

console.log(primeFactor(35)); // 7
console.log(primeFactor(13195)); // 29
console.log(primeFactor(600851475143)); // undefined

Answer 1

问题不在于你的算法它是完全有效的，检查下面稍微修改的算法，我所做的就是用一个参数替换你的起点 Math.floor(x/2)你可以选择:

let isPrime = n => {
        let div = n - 1;
    while (div > 1) {
        if (n % div == 0) return false;
        div--;
    }
    return true;
};

function primeFactor(x, n){
    for (let i = n; i > 1; i--) {
        if (x % i == 0 && isPrime(i) == true) {
            return i;
        }
    }
}

console.log(primeFactor(35, 35));
console.log(primeFactor(13195, 13195));
console.log(primeFactor(600851475143, 100000))

使用上面的方法你会得到一个证明你的实现有效的答案，但是循环太大而无法完成整个事情(即来自 Math.floor(600851475143/2))。假设您的计算机每秒可以执行 5 亿次循环，从 300,425,737,571 到 1 遍历每个循环需要 167 小时，即使每秒循环 50 亿次也需要 16 个半小时。您的方法极度效率低下，但会返回正确答案。您在 JSBin 上没有得到答案的原因更有可能与浏览器/服务限制有关。

---

下面是关于更有效解决方案的剧透

---

以下实现使用素数筛法 ( Sieve of Eratosthenes ) 来生成任何请求的素数列表，然后检查它们是否完全分解为给定的数字，只要您使用足够大的素数列表，这将完全按预期工作。应该注意的是，因为它会生成大量素数列表，如果运行不正确可能会花费一些时间，因此应该生成一个单个素数列表并将其用于下面的所有调用，以及缓存的素数列表最终会因为以后必须执行更少的计算而得到返回:

function genPrimes(n){
  primes = new Uint32Array(n+1);
  primes.fill(1)
  for(var i = 2; i < Math.sqrt(n); i++){
    if(primes[i]){
      for(var j = 2*i; j < n; j+=i){
        primes[j] = 0;
      }
    }
  }
  primeVals = []
  for(var i = 2; i < primes.length; i++){
    if(primes[i]){
      primeVals.push(i);
    }
  }
  return primeVals;
}
    
function primeFactor(x, primes){
  var c = x < primes.length ? x : primes.length
  for (var i = c; i > 1; i--) {
    if(x % primes[i] == 0){
      return primes[i];
    }
  }
}

primes = genPrimes(15487457);
console.log(primeFactor(35, primes));
console.log(primeFactor(13195, primes));
console.log(primeFactor(600851475143, primes));
console.log(primeFactor(30974914,primes));