Find the highest prime factor for given number My code works for some smaller inputs but larger numbers causes it to hang (when running with node)

// The prime factors of 13195 are 5, 7, 13 and 29.
// What is the largest prime factor of the number 600851475143 ?

function factorsOf(n) {
    var factors = [];
    for (var i = 1; i &lt;= n; i++) {
        if (n % i === 0) {
        factors.push(i);
        }
    }
   return factors;
}

function isPrime(number) {
    for (var i=2; i &lt; number; i++) {
    if (number % i === 0) {
        return false;
    }
  }
  return number &gt; 1;
}

function primes(factors) {
    var primes = [];
    for (var i=1; i&lt;factors.length; i++) {
    if (isPrime(factors[i])) {
        primes.push(factors[i]);
    }
  }
  return primes;
}

var factors = factorsOf(13195);
var arr = primes(factors);
console.log(arr[arr.length-1]);
Minor Changes


In factorsOf:


1 is not a proper factor. Start the loop with var i = 2.
n isn't either. Stop the loop with i &lt; n.



Prime Factors

Here is a simple optimization for testing the 'primeness' of a factor. The key is that you have already found a array of factors. Instead of testing every i such that i&lt;n, you can simply test it against the array of factors.

For example, 65 is a factor of 13195. Instead of testing 1 through 64, check to see if any of 13195's other factors divide 65. 65's factors have to also be a factor of 13195 so if it is not prime, there has to exist another factor of 13195 that divides 65.

// Takes a array of proper factors for some number, n,
// and returns a array of the prime factors of n.
// [descriptive function names are a good practice]
function factorsToPrimes(factors) {
    var primes = [];
    // Go through each factor
    for (var i=0; i&lt;factors.length; i++) {
        var iIsPrime = true;
        // Check to see if any other factor divides it
        for (var j=0; j&lt;factors.length; j++) {
            if (factors[i]%factors[j] == 0 &amp;&amp; i != j)
                iIsPrime = false;
        }
        // If no other factor divides it, it must be prime
        if (iIsPrime)
            primes.push(factors[i]);
    }
    return primes;
}


Finding Factors

At this point, factorsOf(n) is the choke point. So if we need to go faster (and we do), we need to fix this.

Factors come in pairs. By definition, a is a factor of n if there is a b such that a*b == n. We also know that the smaller factor is always less than or equal to sqrt(n).

Thus instead of looping from 2 to n, we can loop from 2 to sqrt(n).

// Takes a number, n, and returns a array of 
// all the factors of n.
function factorsOf(n) {
    var factors = [];
    for (var i = 2; i &lt;= Math.sqrt(n); i++) {
        if (n % i === 0) {
            factors.push(i);
            factors.push(n/i);
        }
    }
    return factors;
}


The factor array and the prime factor array aren't necessarily sorted, so the final step is to find the largest prime factor. Here is a concise way to do that using max.

console.log(Math.max.apply(Math, primeFactors)); // Node.js
console.log(Math.max(...primeFactors)); // Or with ECMAScript 6 support


[Note: these changes allow you to get the correct solution (to PE #3) in about a second]



Big O Analysis

[WARNING: Unnecessary technical jargon]

Here is a Big O analysis of you code and these changes. Big O can be useful for finding performance choke points and it is a great tool for "it-works-for-small-input-but-hangs-on-large-input" problems.  So here is a breakdown of your code:


Factors -> O(n)


factorsOf -> O(n)

Prime Factors -> O(n * lg(n))


primes -> O(lg(n))
isPrime -> O(n)

Overall -> O(n * lg(n))


The time spent on finding prime factors grows the fastest. So if we want to go fast, we need to fix this. Then if we want to go faster, we need to improve our factorization. The Big O of these two changes is:


Factors -> O(sqrt(n))


factorsOf -> O(sqrt(n))

Prime Factors -> O(lg(n)^2)


factorsToPrimes -> O(lg(n)^2)

Overall -> O(sqrt(n))