Write factorize(n) -> list[int]: the prime factors of n, with multiplicity, in ascending order. Their product is n. 1 has no prime factors.
1 <= n <= 10^12.
factorize(12) # [2, 2, 3]
factorize(97) # [97]
factorize(1) # []
factorize(360) # [2, 2, 2, 3, 3, 5]
factorize(999_999_000_001) # [999999000001] (a prime near 10^12)
Looping a candidate divisor all the way to n is hopeless for a large prime; aim for O(√n).
Show hint
Divide out each small candidate d as many times as it goes, and stop once d * d > n: whatever is left above 1 at that point has no divisor up to its square root, so it is a single prime.