Prime factorisation of a Number
HardSmallest-prime-factor sieve
Problem
Return the prime factorisation of a number (using a smallest-prime-factor sieve for many queries).
Keep dividing by the smallest factor (2,3,5,...) until you reach 1.
The idea
Precompute the smallest prime factor of every number up to the limit with a sieve, then factorise any number by repeatedly dividing by its stored smallest factor. Each factorisation then costs O(log n) instead of O(√n), which pays off across many queries.
The trick
- Sieve once in O(n log log n), then answer each query in O(log n).
- The number of prime factors with multiplicity is at most log₂(n).
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — 60 Values: 60.
1precompute spf[] via sieve2while n>1: factor=spf[n]; add factor; n/=factorInput
- array
- [60]
Output
- answer
- —
Check yourself
2 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 12
- Output:
- [2, 2, 3]
- Explanation:
- 12 = 2 x 2 x 3.
Example 2
- Input:
- n = 60
- Output:
- [2, 2, 3, 5]
- Explanation:
- 60 = 2 x 2 x 3 x 5.
Example 3
- Input:
- n = 13
- Output:
- [13]
- Explanation:
- 13 is prime.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.