Finding the Prime Factorization

In this lesson you'll learn the algorithm for prime factorization, expressing a number as a product of primes, so you can experience the connection between math and programming. This is for people searching "JavaScript prime factorization" who landed here.

Prime factorization means expressing a number as a product of primes. You find it with the procedure: try dividing starting from 2, and keep dividing by that number for as long as it divides evenly. The result of a prime factorization can also be applied as another way to find the greatest common divisor or least common multiple.

The sample code increases a variable called d starting from 2, dividing n by it for as long as it divides evenly. Once it no longer divides evenly, d is increased by 1 to try the next number — repeating this procedure until n becomes 1 collects every prime factor into an array called factors. Try it with 60 and 97 (which is prime) to see the difference in the results.

A common beginner stumbling block is the difference in role between the inner and outer loops. The inner loop asks "how many times can this same number divide evenly," while the outer loop (while) is responsible for "advancing to the next number to try." Understanding this two-stage structure reveals how the whole algorithm flows.

This is an important idea spanning both math and computer science, forming the very basis for the security of cryptographic technologies (like RSA encryption). It's a subject that lets you directly feel the connection between the fundamental theory of computer science and programming.