Prime factorization
Medium TimeO(√n) SpaceO(log n)
Every whole number above 1 is a product of primes in exactly one way apart from ordering, so 360 is 2 × 2 × 2 × 3 × 3 × 5. Given an integer n greater than 1, return those primes in ascending order, repeating each as many times as it divides. The factors multiply back to exactly n.
Examples
Example 1
- Input
- n = 360
- Output
[2,2,2,3,3,5]2 × 2 × 2 × 3 × 3 × 5 = 360, with 2 dividing three times over.
Example 2
- Input
- n = 97
- Output
- 97 is prime, so it is its own only factor.
[97]
The Code
function primeFactors(n) {
const factors = [];
let d = 2;
while (d * d <= n) {
while (n % d === 0) {
factors.push(d);
n = n / d;
}
d++;
}
if (n > 1) factors.push(n);
return factors;
}
primeFactors(360);Done
More like this
All math & numbers examples (8) →- Prime check Only test odd divisors, and only up to the square root.
- Prime sieve Cross out every multiple; whatever survives is prime.
- Happy number Sum the squared digits until you reach 1 — or start repeating.
- Roman → integer Subtract when a smaller symbol sits before a bigger one.
- Integer → Roman Greedily take the largest symbol that still fits.
- Collatz Halve it if even, triple-plus-one if odd — always reaches 1.