Prime Factors

Every whole number above 1 can be written as a product of primes in exactly one way, apart from the order: 360 = 2 * 2 * 2 * 3 * 3 * 5.

Write prime_factors(n) that returns the prime factors of n as a list sorted from smallest to largest, with each prime repeated as many times as it divides n. For n = 1 return an empty list.

Examples

prime_factors(12)     # returns [2, 2, 3]
prime_factors(97)     # returns [97]
prime_factors(360)    # returns [2, 2, 2, 3, 3, 5]
prime_factors(1)      # returns []

Constraints

• 1 <= n <= 10^12
• n can be a prime close to 10^12, so trying every number up to n is far too slow.