Is this an efficient/correct way to get largest Prime factor?

Question

Is this an efficient way to get the largest prime factor of a given number? Other solutions I found involved nested algorithms.

function largestPrimeFactor(number) {
  const factors = []
  for(let i = 2; i <= number; i++){
    if(number % i === 0){
      factors.push(i);
      number = number / i;
      i = 1;
    }
  }
  return factors.pop()
}

Answer 1

Let's consider a few possible ways to speed this up.

Only look for prime factors

First of all, we know that even numbers (other than 2) are all composites, not primes. So, once we check for 2 as a factor, we can ignore all the other even numbers.

if (number % 2 == 0)
    factors.push(2);

for (int i=3; i<limit; i+=2) {
    if (number % i == 0)
        factors.push(i);
}

This will normally approximately double speed in return for minimal effort.

Limit the search for factors

Note that in the loop above, I've specified the upper limit on the loop as limit rather than number. There's a reason for that. If two numbers multiply to give a third number, at least one of the factors must be less than or equal to the square root of the result. If it's a perfect square, then both of those can be the square root of the number. Otherwise, one is smaller than the square root, and the other is larger than the square root.

But we don't have to conduct a long search for the second number--once we know the factor that's smaller than the square root, simple division tells us the other factor.

So, we can search only for factors less than or equal to the square root, and using them, we can directly find the factors that are larger than the square root.

Also note one other point: there can only be (at most) one prime factor larger than the square root.

Consider using a sieve

Taking the two preceding points together, we can see another possibility. In particular, we can start by searching for primes less than or equal to the input number. Then we can test whether the number is divisible by them (and not any composites).

There's a really fast algorithm for finding all the primes up to some limit called the Sieve of Eratosthenes. It doesn't involve doing an division (which is a slow operation for computers). Instead, consider starting with a table of all the numbers up to the limit you care about. Starting from 2, add 2 to your list of primes numbers, then cross off all the multiples of 2. The look for the next number that isn't crossed off (3 in this case). Add it to the list of primes, then cross off all the multiples of 3. Then repeat--look for the next number that isn't crossed off (5), add it to the list of primes, and cross off all of its multiples.

When you've gone through the whole table that way, you have a list of all the prime numbers up to the limit you care about. Then in your original loop turns into something like:

for (int i=0; i<numberOfPrimes; i++)
    if (number % primes[i] == 0)
        factors.push(primes[i]);

Although it's written in C++ rather than JavaScript, I posted some code to implement this algorithm on SO some years ago. Most of the code isn't very specific to C++ though, so converting to JavaScript should be fairly easy.

This may fall within what you're referring to as a "nested algorithm" though--I'm not entirely sure what you mean by that.

Answer 2

A short review;

this looks great to me

• The last statement could use a semi-colon
• There is no reason to keep all the factors, just keep the last one you find;

function largestPrimeFactor(number) {
  let factor;
  for(let i = 2; i <= number; i++){
    if(number % i === 0){
      factor = i;
      number = number / factor;
      i = 1;
    }
  }
  return factor;
}

console.log(largestPrimeFactor(1));
console.log(largestPrimeFactor(7));
console.log(largestPrimeFactor(60));

Answer 3

No, it's not efficient.

Let's look at your loop, just cleaned up as suggested already:

  for (let i = 2; i <= n; i++) {
    if (n % i === 0) {
      factors.push(i);
      n /= i;
      i = 1;
    }
  }

Let's say you get to the prime i = 97 and find that it's a factor. Why do you then go back to i = 2 (via i = 1 and i++)? Makes no sense. You only got to i = 97 because all smaller i weren't factors. So why check them again? They don't magically become factors.

You could do i-- instead, so that you check the factor again, in case it divides the given number multiple times. Or just use while instead of if, and don't interfere with the for-loop's managing of i.

It's enough to search until \$\sqrt{n}\$, and that's much faster. If \$i > \sqrt{n}\$ divides \$n\$, then \$n/i\$ also does. And it's smaller than \$i\$, so you would've found it and divided it out of \$n\$ already. Well, unless \$i = n\$, because then \$n/i\$ is \$1\$, and the search only started at \$2\$. So after searching only as long as \$i \le \sqrt{n}\$, the remaining \$n\$ itself is also a candidate.

For example, for n=1,000,000,007 your code takes several seconds. The improved solution only takes about a millisecond:

function largestPrimeFactor(n) {
  result = null;
  for (let i = 2; i <= n / i; i++) {
    while (n % i === 0) {
      result = i;
      n /= i;
    }
  }
  return n > 1 ? n : result;
}

t0 = performance.now();
result = largestPrimeFactor(1000000007);
t1 = performance.now();
console.log(t1 - t0, "ms");
console.log(result);

Answer 4

Which algorithm to use?

These types of question often become a list of algorithms rather than a code reviews. If you are after alternative solutions there are dozens online in every language to pick from.

JavaScript Algorithms and Data Structures is a very well documented list of Javascript implementations of many of the most common algorithms (and not so common) including source code (though they use a rather long form style). A handy reference for any coder.

Review

• Storage Using an array to store only the last processed value is rather wasteful. You need only store the last factor as a number, not push it to an array.

• Iteration The use of a for loop should be reserved to iteration of constant sequential interval. Use while loops when this is not so as they give you better control over the counter. (For loops force incrementer update often resulting in more iterations than needed).

• Style Spaces help readability. Generally

  • Spaces after flow control tokens (flow are words like while, for, if, else, and so on).
  • Spaces between operators +, - etc... which you have done.
  • Spaces between code delimiter tokens like ) {,

• Short form Use the short form where possible. Over time programming languages tend to work like natural languages with common oft used words and phrases becoming shorter. JavaScript had the advantage of a late starter ~1994 and came with many of these already built in.

  • Always try to use the shortened form of a programming statement or expression. For example number = number / i; is the same as number /= i;

  • Unlike many compiled languages JavaScript execution order is always known letting you craft even shorter expressions. See example Note that I group the compound expression num /= factor = i, i = 2 using () which is strictly not needed but put there for clarity of intent.

  • Use common abbreviations when you can. Eg number can be num we all know what it means. If you have control of the function name maybe use max rather than largest largestPrimeFactor becomes maxPrimeFactor

  • In the example I use a ternary operator ?. It is debatable whether to use the shorter positive statement i % 0 over i % 0 === 0 as the shorter form relies on the coercion of the statement's expression result to a boolean, while the longer form the boolean is implied and execution is a little quicker. Maybe the longer form is worth while if you are expecting inputs of very large values > 40 bits

The rewrite

The rewrite uses the same algorithm with only some style and storage changes.

There is a performance gain mostly due to the removal of the array. And a little by removal of the for loop incrementer allowing the counter to be reset to 2 rather than 1

console.log([10, 11, 12, 17, 42, 81, 119, -133, 5.2].map(maxPrimeFactor) + "");


   
function maxPrimeFactor(num) { // num is expected as an unsigned integer
    var factor, i = 2;
    while (i <= num) {
        num % i ? i++ : (num /= factor = i, i = 2);
    }
    return factor;
}

//Personally I always collapse single line blocks. Keeping the block delimiters {}
function maxPrimeFactor(num) {
    var factor, i = 2;
    while (i <= num) { num % i ? i++ : (num /= factor = i, i = 2) }
    return factor;
}

// As i have been accused in the comments of abusing ternaries you can also 
// use a short circuit expression 
function maxPrimeFactor(num) {
    var factor, i = 2;
    while (i <= num) { (num % i && i++) || (num /= factor = i, i = 2) }
    return factor;
}