Greatest Prime Factor

Question

I'm trying to complete an algorithm challenge to find the largest prime factor of 600851475143. I'm not necessarily asking for the answer. Just trying to figure out why this code isn't working. Why does it return 'undefined' instead of a number?

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

The problem is not your algorithm it is perfectly valid, check the below slightly modified algorithm, all I've done is replaced your starting point Math.floor(x/2) with a parameter that you can choose:

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))

Using the above you'll get an answer that proves your implementation works, but the loop is too big to do the entire thing(i.e. from Math.floor(600851475143/2)). Say your computer can do 500million loops per second, going through every one from 300,425,737,571 down to 1 would take 167 hours, even at 5 billion loops per second it would take 16 and a half hours. Your method is extremely inefficient but will return the correct answer. The reason you're not getting an answer on JSBin is more likely to do with browser/service limitations.

---

Spoilers on more efficient solution below

---

The following implementation uses a prime sieve(Sieve of Eratosthenes) in order to generate any list of primes requested and then checks if they fully factor into the given number, as long as you use a large enough list of primes, this will work exactly as intended. it should be noted that because it generates a large list of primes it can take some time if ran incorrectly, a single list of primes should be generated and used for all calls below, and the cached list of primes will pay off eventually by having to perform less calculations later on:

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));

Answer 2

let primeFactor = x => {
    if (x === 1 || x === 2) {
        return x;
    }

    while (x % 2 === 0) {
        x /= 2;
    }
    
    if (x === 1) {
        return 2;
    }

    let max = 0;
    for (let i = 3; i <= Math.sqrt(x); i += 2) {
        while (x % i === 0) {
            x /= i;
            max = Math.max(i, max);
        }
    }

    if (x > 2) {
        max = Math.max(x, max);
    }
    
    return max;
};

console.log(primeFactor(35));
console.log(primeFactor(13195));
console.log(primeFactor(27));
console.log(primeFactor(1024));
console.log(primeFactor(30974914));
console.log(primeFactor(600851475143));

Optimizations

• Dividing the number by 2 until it's odd since no even number is prime.

• The iteration increment is 2 rather than 1 to skip all even numbers.

• The iteration stops at sqrt(x). The explanation for that is here.