Prime Factorisation

Easy
173.

Prime Factorisation

Prime Factorisation is an easy coding problem on math and number theory, asked in TCS, Infosys, Wipro and HCL interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number[]}
 */
var primeFactors = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Divide out each candidate d completely before moving on — that guarantees every d you find is prime.

  2. Hint 2

    You only need to test d while d * d <= n, because at most one prime factor can exceed √n.

  3. 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

  1. Start d = 2.
  2. While d * d <= n: while d divides n, append d and divide; then increment d.
  3. If n > 1 remains, 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 > 1 drops the largest prime — 14 would return [2].
  • Incrementing d by 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 out

Java

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.

All 337 math problems · the whole catalogue