46 lines
1.2 KiB
Python
46 lines
1.2 KiB
Python
from math import sqrt
|
|
from functools import lru_cache, reduce
|
|
from collections import Counter
|
|
from itertools import product
|
|
|
|
|
|
MUL = int.__mul__
|
|
|
|
|
|
def prime_factors(n):
|
|
'Map prime factors to their multiplicity for n'
|
|
d = _divs(n)
|
|
d = [] if d == [n] else (d[:-1] if d[-1] == d else d)
|
|
pf = Counter(d)
|
|
return dict(pf)
|
|
|
|
@lru_cache(maxsize=None)
|
|
def _divs(n):
|
|
'Memoized recursive function returning prime factors of n as a list'
|
|
for i in range(2, int(sqrt(n)+1)):
|
|
d, m = divmod(n, i)
|
|
if not m:
|
|
return [i] + _divs(d)
|
|
return [n]
|
|
|
|
|
|
def proper_divs(n):
|
|
'''Return the set of proper divisors of n.'''
|
|
pf = prime_factors(n)
|
|
pfactors, occurrences = pf.keys(), pf.values()
|
|
multiplicities = product(*(range(oc + 1) for oc in occurrences))
|
|
divs = {reduce(MUL, (pf**m for pf, m in zip(pfactors, multis)), 1)
|
|
for multis in multiplicities}
|
|
try:
|
|
divs.remove(n)
|
|
except KeyError:
|
|
pass
|
|
return divs or ({1} if n != 1 else set())
|
|
|
|
|
|
if __name__ == '__main__':
|
|
rangemax = 20000
|
|
|
|
print([proper_divs(n) for n in range(1, 11)])
|
|
print(*max(((n, len(proper_divs(n))) for n in range(1, 20001)), key=lambda pd: pd[1]))
|