Prime Factorization

Problem

Return the prime factorization of n as a list of [prime, exponent] pairs sorted by prime in ascending order.

Divide out each candidate factor up to the square root, counting repetitions, and treat any remaining value greater than 1 as a final prime factor. Return an empty list for n = 1.

Hint

After dividing out all smaller factors, what remains above the square root must be prime.

Test cases

case 1

in: [12]

expected: [[2,2],[3,1]]

case 2

in: [1]

expected: []

case 3

in: [97]

expected: [[97,1]]

case 4

in: [360]

expected: [[2,3],[3,2],[5,1]]

case 5

in: [100]

expected: [[2,2],[5,2]]

Starter codePython

def prime_factorization(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor