Prime Factorization

Given an integer $N$, return its prime factorization as a list of prime factors. For example, $12 = 2 \times 2 \times 3$, so the output is [2, 2, 3]. $N = 1$ returns an empty list.

Repeatedly divide $N$ by the smallest possible prime factor. Start with 2 (to handle all even factors), then check only odd numbers from 3 to $\sqrt{N}$. If $N > 1$ after the loop, the remaining value is itself a prime factor (the largest one).

1. Initialize an empty list factors.
2. While $N$ is divisible by 2, append 2 and divide $N$ by 2.
3. For odd divisors $i = 3, 5, 7, \ldots$ up to $\sqrt{N}$: while $N$ is divisible by $i$, append $i$ and divide.
4. If $N > 1$ after the loop, $N$ is a prime — append it.

• Only dividing by each factor once instead of looping (misses repeated factors, e.g., 12 = 2 × 2 × 3)
• Not handling the "remaining prime" case after the loop — e.g., 14 = 2 × 7; after dividing by 2, n = 7 > 1, so 7 must be appended
• Checking only up to $\sqrt{\text{original } N}$ instead of dynamically comparing to $i^2 \leq n$ (the latter is correct since $n$ shrinks)

Prime factorization underlies RSA encryption: factoring a large number $N = p \times q$ is computationally infeasible for huge primes, while multiplying them is easy. The "remaining prime" optimization after the loop is elegant — it's the key insight that keeps this solution correct and $O(\sqrt{N})$.