4
\$\begingroup\$

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 <= n; i++) {
        if (n % i === 0) {
        factors.push(i);
        }
    }
   return factors;
}

function isPrime(number) {
    for (var i=2; i < number; i++) {
    if (number % i === 0) {
        return false;
    }
  }
  return number > 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]);
\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is code review. That board you quote is like the Rosetta Stone website. Here he wants us to review his code, and I didn't see a Javascript solution to the link you provided. Moderator should not accept this flag. \$\endgroup\$ Feb 21, 2017 at 22:00

4 Answers 4

4
\$\begingroup\$

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

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 <= 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))
\$\endgroup\$
3
  • \$\begingroup\$ It appears ... is unsupported by node v4.0.0 But I can see the speed increases by only iterating upto the sqrt(n) \$\endgroup\$
    – Luke
    Feb 22, 2017 at 10:57
  • 1
    \$\begingroup\$ @Luke: Math.max.apply(null, primeFactors) can be in that case \$\endgroup\$
    – Craig Ayre
    Feb 22, 2017 at 14:13
  • 1
    \$\begingroup\$ @Luke Good catch! I forgot we were working with Node. \$\endgroup\$ Feb 22, 2017 at 14:44
1
\$\begingroup\$

I think you can make some simplifications by using the prime factors algorithm and take into account multiple factors: For example 40 is 2*2*2*5. To do this, each time you find a factor, you divide the remainder by the factor and recheck the factor as many times as necessary.

function primeFactorsOf(number) {
  assert(number>0);
  let remainder = number;
  let results = [];

  let i = 2, lastPrime;
  while (i <= remainder) {
    if (remainder % i == 0) {
      remainder = remainder / i;

      // Only store a single prime
      // For example the prime factors of 20 are 2 and 5
      if (i != lastPrime) {
        results.push(i);  
        lastPrime = i;
      }   
    } else {
      i++;
    }
  }

  assert(remainder == 1);
  return results;
}

console.log('results',    20, primeFactorsOf(   20) );
console.log('results', 13195, primeFactorsOf(13195) );
console.log('results', 600851475143, primeFactorsOf(600851475143) );

Its not necessary to check if the number is prime since non-primes are removed automatically by the division.

For large numbers you could also improve it further by checking for factors of two before the while loop and then stepping in increments of 2 since multiples of 2 are never prime.

while (remainder % 2 == 0) {
  remainder = remainder / 2;
  if (!results.length) results.push(2)
}

let i = 3, lastPrime;
while (i <= remainder) {
    ...
  else {
    i += 2
  }
}
\$\endgroup\$
2
  • \$\begingroup\$ I am disappointed that this answer, which makes the crucial observation that it is not necessary to test factors for primality, did not get selected. Here are two other answers where I make the same point. \$\endgroup\$ Feb 22, 2017 at 15:37
  • \$\begingroup\$ Possibly because I posted afterwards :) I would be interested to see a performance comparison. \$\endgroup\$ Feb 22, 2017 at 18:54
0
\$\begingroup\$

NonlinearFruit is certainly right that you only have to check up until the square root of the number. But there are more improvements we can make.

First, we only care about primes. If we're checking 42, we don't care that 6 is a factor; it's not really relevant to us. So, we should only check for prime factors. At the start of your program, make a global array (or a local one if you want, you'll just have to pass it around a lot) of every prime up until the square root of the number. Here would be my code:

var allPrimes = [];

function isPrime(number) {
    for (var i=0; i < allPrimes.length; i++) {
        if (number % allPrimes[i] === 0) {
            return false;
        }
    }
    return number > 1;
}

function defineAllPrimesTo(number) {
    for (var i = 2; i <= number; i++) {
        if (isPrime(i)) allPrimes[allPrimes.length] = i;
    }
}

Now we can make the allPrimes array. This makes everything else quicker. However, I also think it's worth changing how you find the biggest prime: instead of finding all the factors, just get rid of every smaller prime factor you can until you've gone through every prime factor up until the square root of the number you're finding. This will leave you with the number you want:

function findBiggestPrimeFactor(number) {
    defineAllPrimesTo(Math.sqrt(number));
    for (var i = 0; allPrimes[i] <= Math.sqrt(number); i++ {
        if (number % allPrimes[i] == 0) {
            number = number / allPrimes[i];
            i -= 1;
        }
    }
    return number;
}

The only interesting detail (in my eyes) is that i -= 1. That's necessary because if a number is a factor of 4, for example, if we just divide it by 2 once, that won't suffice. For the rest of the problem, there'll be a hanging multiple of 2 (it's the Bush v. Gore of prime factors). This way, we recheck that same prime, so if we had 12, for example, we'd divide it by 2, check if it's divisible by 2 (it will be), and divide it again by 2.

This should make it more efficient. Please let me know if I can be of any more help.

\$\endgroup\$
4
  • \$\begingroup\$ If we only find a prime upto the sqrt(n) aren't we missing that a larger prime could exist? E.g 29 is a prime factor of 58 but much larger than sqrt(58) \$\endgroup\$
    – Luke
    Feb 22, 2017 at 11:01
  • \$\begingroup\$ I belive this was covered in Nonlinearfruits review by also adding the paired factor. You may be doing this but I can't work out where. \$\endgroup\$
    – Luke
    Feb 22, 2017 at 11:26
  • \$\begingroup\$ If we were to do 58, the program would divide by 2, get 29, go up to 5, find that none of them are factors, and return 29. \$\endgroup\$ Feb 22, 2017 at 18:51
  • \$\begingroup\$ For a more formal proof, assume you have a number n with no factors less than sqrt(n). Then, if we say that it has a factor greater than sqrt(n), this factor has to have that ordered pair. However, because n has no factor less than the sqrt(n), it's pair has to be greater than sqrt(n) as well. However, this can't be the case - if you multiply those two together, the result would be greater than n, because both are greater than sqrt(n), and sqrt(n)^2 is n. Therefore, any number with no factors less than sqrt(n) is prime. \$\endgroup\$ Feb 22, 2017 at 18:56
0
\$\begingroup\$

You can also consider using generators which are slightly more slower that the iterating method but have less memory requirements.

Here is an example:

function *factors(n){
  let index = 2;

  while (index < Math.sqrt(n)) {
    if (n % index === 0) {
      yield index;
      yield n / index;
    }

    index += 1;
  }
}

Use like:

for (let factor of factors(600851475143)) {
   console.log(factor)
}
\$\endgroup\$
2
  • \$\begingroup\$ Generators could be part of a nice solution, and the overhead would be negligible if you had a good algorithm. Unfortunately, this strategy is poor, and will take forever to run. See this answer for a discussion. \$\endgroup\$ Feb 22, 2017 at 15:41
  • \$\begingroup\$ You are right. For finding a single value such as the largest prime factor generators does not work well and we need a different strategy \$\endgroup\$ Feb 22, 2017 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.