Prime Factorization Explained

Problem Statement

Given a positive integer n, return its prime factorization, i.e., a list of prime numbers that multiply to give n. For example, the prime factorization of 12 is [2, 2, 3] since 2 * 2 * 3 = 12. This problem tests your ability to identify prime factors efficiently.

Example

Input: n = 12

Output: [2, 2, 3]

Explanation: 12 = 2 * 2 * 3.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List primeFactorization(int n) {
        List factors = new ArrayList<>();
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                factors.add(i);
                n /= i;
            }
        }
        if (n > 1) factors.add(n);
        return factors;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.primeFactorization(12)); // [2, 2, 3]
    }
}
            

def prime_factorization(n):
    factors = []
    i = 2
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += 1
    if n > 1:
        factors.append(n)
    return factors

# Example usage
print(prime_factorization(12))  # [2, 2, 3]
            

function primeFactorization(n) {
    const factors = [];
    for (let i = 2; i * i <= n; i++) {
        while (n % i === 0) {
            factors.push(i);
            n /= i;
        }
    }
    if (n > 1) factors.push(n);
    return factors;
}

// Example usage
console.log(primeFactorization(12)); // [2, 2, 3]
            

Explanation

• Start with the smallest prime, 2, and check divisibility.
• While n is divisible by i, add i to the factors and divide n by i.
• Increment i up to the square root of n.
• If n remains greater than 1, it is a prime factor itself.
• Return the list of factors.

Note