Module gopy.dfs.all_factors
Numbers can be regarded as product of its factors. For example, 8 = 2 x 2 x 2; = 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.Numbers can be regarded as product of its factors. For example, 8 = 2 x 2 x 2; = 2 x 4.
Examples: input: 1 output: []
input: 37 output: []
input: 32 output: [ [2, 16], [2, 2, 8], [2, 2, 2, 4], [2, 2, 2, 2, 2],
Expand source code
"""
Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
= 2 x 4.
Write a function that takes an integer n and return all possible combinations
of its factors.Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
= 2 x 4.
Examples:
input: 1
output:
[]
input: 37
output:
[]
input: 32
output:
[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
"""
def get_factors(n):
"""[summary]
Arguments:
n {[int]} -- [to analysed number]
Returns:
[list of lists] -- [all factors of the number n]
"""
def factor(n, i, combi, res):
"""[summary]
helper function
Arguments:
n {[int]} -- [number]
i {[int]} -- [to tested divisor]
combi {[list]} -- [catch divisors]
res {[list]} -- [all factors of the number n]
Returns:
[list] -- [res]
"""
while i * i <= n:
if n % i == 0:
res += combi + [i, int(n/i)],
factor(n/i, i, combi+[i], res)
i += 1
return res
return factor(n, 2, [], [])
def get_factors_iterative1(n):
"""[summary]
Computes all factors of n.
Translated the function get_factors(...) in
a call-stack modell.
Arguments:
n {[int]} -- [to analysed number]
Returns:
[list of lists] -- [all factors]
"""
todo, res = [(n, 2, [])], []
while todo:
n, i, combi = todo.pop()
while i * i <= n:
if n % i == 0:
res += combi + [i, n//i],
todo.append((n//i, i, combi+[i])),
i += 1
return res
def get_factors_iterative2(n):
"""[summary]
analog as above
Arguments:
n {[int]} -- [description]
Returns:
[list of lists] -- [all factors of n]
"""
ans, stack, x = [], [], 2
while True:
if x > n // x:
if not stack:
return ans
ans.append(stack + [n])
x = stack.pop()
n *= x
x += 1
elif n % x == 0:
stack.append(x)
n //= x
else:
x += 1Functions
def get_factors(n)-
[summary]
Arguments
n {[int]} – [to analysed number]
Returns
[list of lists] – [all factors of the number n]
Expand source code
def get_factors(n): """[summary] Arguments: n {[int]} -- [to analysed number] Returns: [list of lists] -- [all factors of the number n] """ def factor(n, i, combi, res): """[summary] helper function Arguments: n {[int]} -- [number] i {[int]} -- [to tested divisor] combi {[list]} -- [catch divisors] res {[list]} -- [all factors of the number n] Returns: [list] -- [res] """ while i * i <= n: if n % i == 0: res += combi + [i, int(n/i)], factor(n/i, i, combi+[i], res) i += 1 return res return factor(n, 2, [], []) def get_factors_iterative1(n)-
[summary] Computes all factors of n. Translated the function get_factors(…) in a call-stack modell.
Arguments
n {[int]} – [to analysed number]
Returns
[list of lists] – [all factors]
Expand source code
def get_factors_iterative1(n): """[summary] Computes all factors of n. Translated the function get_factors(...) in a call-stack modell. Arguments: n {[int]} -- [to analysed number] Returns: [list of lists] -- [all factors] """ todo, res = [(n, 2, [])], [] while todo: n, i, combi = todo.pop() while i * i <= n: if n % i == 0: res += combi + [i, n//i], todo.append((n//i, i, combi+[i])), i += 1 return res def get_factors_iterative2(n)-
[summary] analog as above
Arguments
n {[int]} – [description]
Returns
[list of lists] – [all factors of n]
Expand source code
def get_factors_iterative2(n): """[summary] analog as above Arguments: n {[int]} -- [description] Returns: [list of lists] -- [all factors of n] """ ans, stack, x = [], [], 2 while True: if x > n // x: if not stack: return ans ans.append(stack + [n]) x = stack.pop() n *= x x += 1 elif n % x == 0: stack.append(x) n //= x else: x += 1