Prime Factorization of a Number
Solve this Problemn, return its prime factorization as a list — every prime that divides n, repeated as many times as it divides it, in ascending order.
A composite number always has a factor at or below its own square root, so trial division never needs to test past √n — and once nothing else divides evenly, whatever is left over (if greater than 1) is itself prime.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 10⁹
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Linear Scan
BruteTry every candidate from 2 up to n. Whenever the current candidate divides the running value evenly, divide it out and record the candidate — repeating until it no longer divides — then move to the next candidate. Correct, but for a prime n nothing divides it until the candidate reaches n itself, so the loop pays for the full range.
O(n)O(1) extra1class Solution {
2 public int[] primeFactors(int n) {
3 List<Integer> factors = new ArrayList<>();
4 int num = n;
5 for (int i = 2; i <= n && num > 1; i++) {
6 while (num % i == 0) {
7 factors.add(i);
8 num /= i;
9 }
10 }
11 int[] result = new int[factors.size()];
12 for (int j = 0; j < result.length; j++) {
13 result[j] = factors.get(j);
14 }
15 return result;
16 }
17}Optimal — Trial Division up to √n
OptimalA composite number always has a factor at or below its own square root, so trial division only needs candidates up to √(what's left of n), not up to n itself — and that bound shrinks every time a factor is divided out. Once the loop ends, whatever remains in n (if anything greater than 1) has no factor of its own below its square root, which means it must itself be prime — so it's appended as the final factor.
O(√n)O(number of prime factors)1class Solution {
2 public int[] primeFactors(int n) {
3 List<Integer> factors = new ArrayList<>();
4 int num = n;
5 for (int i = 2; (long) i * i <= num; i++) {
6 while (num % i == 0) {
7 factors.add(i);
8 num /= i;
9 }
10 }
11 if (num > 1) {
12 factors.add(num);
13 }
14 int[] result = new int[factors.size()];
15 for (int j = 0; j < result.length; j++) {
16 result[j] = factors.get(j);
17 }
18 return result;
19 }
20}