# Prime Factorization of a Number

☰ Table of Content

# Problem Statement

How do we find all the prime factors of a given number?

For example, when `n = 12`, the output should be `[2, 3]`. Notice that `1, 4, 6, 12` are also factors of 12 but they aren’t prime and therefore should be excluded from the output.

## Solution

The following solution is straghtforward:

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````def get_prime_factors(n: int) -> List[int]: prime_factors = [] prime = 2 while n > 1: while n % prime == 0: if not prime_factors or prime != prime_factors[-1]: # deduplicate prime_factors.append(prime) n //= prime prime += 1 return prime_factors ``````

## 2 Keys Keyboard

This problem is an application of the prime factorization algorithm:

 ``````1 2 3 4 5 6 7 8 9 `````` ``````def minSteps(n: int) -> int: prime = 2 steps = 0 while n > 1: while n % prime == 0: steps += prime n //= prime prime += 1 return steps ``````

## Count Ways to Make Array With Product

This problem is a more involved application of the prime factorization algorithm. To understand the below algorithm, please review https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)#Theorem_two_2.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 `````` ``````from math import comb class Solution: def waysToFillArray(self, queries: List[List[int]]) -> List[int]: res = [] for n, k in queries: powers = self.total_power(k) ans = 1 for p in powers: ans *= self.count_sum_up(n, p) res.append(ans) return res def total_power(self, n: int) -> int: res = [] prime = 2 while n > 1: power = 0 while n % prime == 0: power += 1 n //= prime if power > 0: res.append(power) prime += 1 return res def count_sum_up(self, n: int, total: int) -> int: return comb(n + total - 1, n - 1) ``````

Note that the above code will not be accepted by leetcode. I’ve omitted two details: 1) the answers should modulo `10^9 + 7` and 2) we need to memoize methods `total_power` and `count_sum_up`. The omissions are intentional so the attention can be focused on the main logic.

One of the constraints of the problem states that each `k` does not exceed `10^4`. We can further optimize by precomputing all primes less than or equal to `10^4`:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 `````` ``````class Solution: def waysToFillArray(self, queries: List[List[int]]) -> List[int]: self.primes = self.get_primes_at_most(10000) res = [] for n, k in queries: powers = self.total_power(k) ans = 1 for p in powers: ans *= self.count_sum_up(n, p) res.append(ans) return res def total_power(self, n: int) -> int: res = [] prime = 2 for prime in self.primes: if prime > n: break power = 0 while n % prime == 0: power += 1 n //= prime if power > 0: res.append(power) return res def count_sum_up(self, n: int, total: int) -> int: return comb(n + total - 1, n - 1) % (pow(10, 9) + 7) def get_primes_at_most(self, n: int) -> List[int]: primes = [] nums = [True] * (n + 1) for i in range(2, n + 1): if nums[i]: primes.append(i) nums[i] = False for j in range(i * i, n, i): nums[j] = False return primes ``````

Method `get_primes_at_most` is an implementation of Sieve of Eratosthenes. Refer to this post for more details.

Update: 2021-11-17