Medium · Repeated Trial Division
Understand → Visualise → Practice.
Return the prime factors of positive n in nondecreasing order, including repeated factors.
Try divisors from 2 upwards. Each time d divides n, record d and divide it out. Because smaller factors go first, every recorded d is prime.
While n % d == 0, append d and set n //= d.
Move d up while d × d ≤ n.
If n > 1 at the end, it is a prime factor larger than √(original n).
O(√n) time and O(log n) space for the factors.
Forgetting the leftover loses a large prime factor, e.g. 14 = 2 × 7.
Read the full guide first: Number Theory Basics for Algorithms.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.