Prime Factorization of a Number
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 straightforward:
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

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

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.