FilesExpand file tree

 master

/

factor_combinations.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

63 lines (55 loc) · 1.09 KB

 master

/

factor_combinations.py

Copy path

Top

File metadata and controls

• Code
• Blame

63 lines (55 loc) · 1.09 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

"""

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.

Note:

You may assume that n is always positive.

Factors should be greater than 1 and less than n.

Examples:

input: 1

output:

[]

input: 37

output:

[]

input: 12

output:

[

[2, 6],

[2, 2, 3],

[3, 4]

]

input: 32

output:

[

[2, 16],

[2, 2, 8],

[2, 2, 2, 4],

[2, 2, 2, 2, 2],

[2, 4, 4],

[4, 8]

]

"""

# Iterative:

def get_factors(n):

todo, combis = [(n, 2, [])], []

while todo:

n, i, combi = todo.pop()

while i * i <= n:

if n % i == 0:

combis.append(combi + [i, n//i])

todo.append((n//i, i, combi+[i]))

i += 1

return combis

# Recursive:

def recursive_get_factors(n):

def factor(n, i, combi, combis):

while i * i <= n:

if n % i == 0:

combis.append(combi + [i, n//i]),

factor(n//i, i, combi+[i], combis)

i += 1

return combis

return factor(n, 2, [], [])