Skip to content
DSA in JavaScript
More Math

Prime Factors

Algorithm · Stretch

Level: StretchNumber Theory

Step through it: Number Theory pattern

a, b
48
18

Step 1 of 5

Goal: the greatest common divisor of 48 and 18. Key fact: the answer stays the same if you replace (a, b) with (b, the remainder of a ÷ b). The numbers shrink quickly.

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.

Image source: Math is Fun

Prime factors are those prime numbers which multiply together to give the original number. For example 39 will have prime factors of 3 and 13 which are also prime numbers. Another example is 15 whose prime factors are 3 and 5.

Image source: Math is Fun

Finding the prime factors and their count accurately

The approach is to keep on dividing the natural number n by indexes from i = 2 to i = n (by prime indexes only). The value of n is being 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 optimisation is achievable when 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 which can divide n completely other than n itself.

Hardy-Ramanujan formula for approximate calculation of prime-factor count

In 1917, a theorem was formulated by G.H Hardy and Srinivasa Ramanujan which states that the normal order of the number ω(n) of distinct prime factors of a number n is log(log(n)).

Roughly speaking, this means that most numbers have about this number of distinct prime factors.

Code

primeFactors.js
/**
 * Finds prime factors of a number.
 *
 * @param {number} n - the number that is going to be split into prime factors.
 * @returns {number[]} - array of prime factors.
 */
export function primeFactors(n) {
  // Clone n to avoid function arguments override.
  let nn = n;

  // Array that stores the 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(nn); factor += 1) {
    // Check that factor divides n without a reminder.
    while (nn % factor === 0) {
      // Overriding the value of n.
      nn /= 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 (nn !== 1) {
    factors.push(nn);
  }

  return factors;
}

/**
 * Hardy-Ramanujan approximation of prime factors count.
 *
 * @param {number} n
 * @returns {number} - approximate number of prime factors.
 */
export function hardyRamanujan(n) {
  return Math.log(Math.log(n));
}

References

Practice

Spotted a mistake or something unclear? Report it on GitHub.

Least common multiple

Algorithm · Stretch

Horner's Method

Algorithm · Stretch

On this page

Finding the prime factors and their count accuratelyHardy-Ramanujan formula for approximate calculation of prime-factor countCodeReferences