Prime Factorization

Break a number into its prime building blocks by dividing out the smallest factor repeatedly. Only trial-divide up to √n; any leftover > 1 is itself prime.

Category: Mathematics
Time complexity: O(√n)
Space complexity: O(1)

Pseudocode

for d from 2 while d² ≤ n
  while d divides n: record d, n ÷= d
if n > 1: n is a prime factor

Reference implementation

for d in range(2, int(n**0.5)+1):
    while n % d == 0:
        factors.append(d); n //= d
if n &gt; 1: factors.append(n)

Open the interactive Prime Factorization visualisation →