patternjavascriptMinor

Find the highest prime factor for given number

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

findthenumberfactorforhighestprimegiven

Problem

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  1;
}

function primes(factors) {
    var primes = [];
    for (var i=1; i<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]);

Solution

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




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

Code Snippets

// 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<factors.length; i++) {
        var iIsPrime = true;
        // Check to see if any other factor divides it
        for (var j=0; j<factors.length; j++) {
            if (factors[i]%factors[j] == 0 && i != j)
                iIsPrime = false;
        }
        // If no other factor divides it, it must be prime
        if (iIsPrime)
            primes.push(factors[i]);
    }
    return primes;
}

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

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

Context

StackExchange Code Review Q#155941, answer score: 4

Revisions (0)

No revisions yet.