factors.py
View source code here on GitHub!
Includes
- python.src.lib.factors.proper_divisors(num: int) Iterator[int]
Iterate over the proper divisors of a given number.
Given that it will generate a max of \(\log(n)\) factors, the binomial theorem tells us this should take \(O(2^{\log(n)}) = O(n)\) operations.
1from functools import reduce
2from itertools import combinations
3from operator import mul
4from typing import Iterator, Set
5
6from .primes import prime_factors
7
8
9def proper_divisors(num: int) -> Iterator[int]:
10 """Iterate over the proper divisors of a given number.
11
12 Given that it will generate a max of :math:`\\log(n)` factors, the binomial theorem tells us this should take
13 :math:`O(2^{\\log(n)}) = O(n)` operations."""
14 factors = tuple(prime_factors(num))
15 seen: Set[int] = set()
16 yield 1
17 for x in range(1, len(factors)):
18 for combo in combinations(factors, x):
19 ret = reduce(mul, combo, 1)
20 if ret not in seen:
21 yield ret
22 seen.add(ret)
23 seen.clear()