Prime Factorisation — Solution in Python, Java & C++
Prime Factorisation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Prime Factorisation is an easy coding problem on math and number theory, asked in TCS, Infosys, Wipro and HCL interviews.
- Difficulty: Easy
- Topics: Math, Number Theory
- Asked at: TCS, Infosys, Wipro, HCL
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n greater than 1, return all of its prime factors in non-decreasing order, repeating a factor as many times as it divides n.
Example 1
Input: n = 12
Output: [2,2,3]
Explanation: 12 = 2 × 2 × 3.
Example 2
Input: n = 97
Output: [97]
Explanation: 97 is prime, so it is its own only factor.
Example 3
Input: n = 100
Output: [2,2,5,5]
Constraints
2 <= n <= 1000000
Hints for Prime Factorisation
Hint 1
Divide out each candidate
dcompletely before moving on — that guarantees everydyou find is prime.Hint 2
You only need to test
dwhiled * d <= n, because at most one prime factor can exceed √n.Hint 3
Whatever is left above 1 after the loop is that last large prime; do not forget to append it.
How to solve Prime Factorisation
Trial division: divide out each candidate d completely before moving on, so every d that divides is guaranteed prime, and stop at √n because at most one prime factor can be larger.
Approach
- Start
d = 2. - While
d * d <= n: whileddividesn, appenddand divide; then incrementd. - If
n > 1remains, append it.
Why it works
When the loop reaches d, all smaller primes have been divided out, so if d divides the remaining n it cannot have a smaller factor — it is prime. After the loop the leftover has no factor ≤ √(original) other than those removed, so it is either 1 or a single prime.
Complexity
- Time —
O(√n) - Space —
O(log n) for the output
Pitfalls
- Forgetting the final
if n > 1drops the largest prime —14would return[2]. - Incrementing
dby one is fine at this scale; skipping evens after 2 is an optional constant-factor win.
Reference solution
Python
def primeFactors(n: int):
out = []
d = 2
while d * d <= n:
while n % d == 0:
out.append(d)
n //= d
d += 1
if n > 1:
out.append(n)
return outJava
public static int[] primeFactors(int n) {
List<Integer> out = new ArrayList<>();
for (int d = 2; (long) d * d <= n; d++) {
while (n % d == 0) {
out.add(d);
n /= d;
}
}
if (n > 1) out.add(n);
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> primeFactors(int n) {
vector<int> out;
for (int d = 2; (long long) d * d <= n; d++) {
while (n % d == 0) {
out.push_back(d);
n /= d;
}
}
if (n > 1) out.push_back(n);
return out;
}JavaScript
var primeFactors = function(n) {
const out = [];
for (let d = 2; d * d <= n; d++) {
while (n % d === 0) {
out.push(d);
n /= d;
}
}
if (n > 1) out.push(n);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.