BinarySearch 0229 Prime Factorization

Problem statement

https://binarysearch.com/problems/Prime-Factorization/

Solution

Just check all numbers before square root of n and continue with recursion.

Complexity

It is O(sqrt(n)) for time and O(log^2n) for space, because we can have O(log n) answer, which we extend by one on each iteration.

Code

class Solution:
    def solve(self, n):
        for i in range(2, int(sqrt(n)) + 1):
            if n % i == 0:
                return [i] + self.solve(n//i)
        return [n]