The Prime Factors algorithm is a very interesting question that you may have heard in your school or college asked in many interviews including FAANG companies.  


The question for an algorithm is,


A prime number is a whole number greater than 1 that cannot be made by multiplying other whole numbers. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, and so on.

If we can make it by multiplying other whole numbers it is a Composite Number.


Example 1:

Input: n=39

Output: [3, 13] 

Explanation: 39 will have prime factors of 3 and 13 which are also prime numbers.


Example 2:

Input: 15

Output: [3,5]

Explanation: 15 have prime factors of 3 and 5 which are also prime numbers.


Let's start with the algorithm,


var  primeFactor = function(n) {

  // Clone n to avoid function arguments override.

  let num = n;

  // Array that stores all the prime factors.

  const factors = [];

  // Running the loop till sqrt(n) instead of n to optimise time complexity from O(n) to O(sqrt(n)).

  for (let factor = 2; factor <= Math.sqrt(num); factor++) {

    // Check that factor divides n without a reminder.

    while (num % factor === 0) {

      // Overriding the value of n.

      num /= factor;

      // Saving the factor.

      factors.push(factor);

    }

  }

  // The ultimate reminder should be a last prime factor,

  // unless it is not 1 (since 1 is not a prime number).

  if (num !== 1) {

    factors.push(num);

  }

  return factors;

};


Here, the approach is to keep on dividing the natural number n by indexes from i=2 to i=n (by prime number only). The value of n is overridden by (n/i) on each iteration.

The time complexity till now is O(n) in the worst-case scenario since the loop runs from index i = 2 to i = n. This time complexity can be reduced from O(n) to O(sqrt(n)). The optimization is achievable when the loop runs from i = 2 to i = sqrt(n). Now, we go only till O(sqrt(n)) because when i becomes greater than sqrt(n), we have the confirmation that there is no index i left that can divide n completely other than n itself.


I hope you understood the algorithm. If you have any doubts, please let us know in the comments.