Anonymous user
Proper divisors: Difference between revisions
→{{header|Python}}: Add prime factor based version.
(+Java) |
(→{{header|Python}}: Add prime factor based version.) |
||
Line 56:
15120: 79</pre>
=={{header|Python}}==
===Python: Literal===
A very literal interpretation
<lang python>>>> def proper_divs2(n):
Line 69 ⟶ 70:
79
>>> </lang>
===Python: From prime factors===
I found [http://stackoverflow.com/a/171784/10562 a reference] on how to generate factors from all the prime factors and the number of times each prime factor goes into N - its multiplicity.
For example, given N having prime factors P(i) with associated multiplicity M(i}) then the factors are given by:
<pre>
for m[0] in range(M(0) + 1):
for m[1] in range(M[1] + 1):
...
for m[i - 1] in range(M[i - 1] + 1):
mult = 1
for j in range(i):
mult *= P[j] ** m[j]
yield mult</pre>
This version is over an order of magnitude faster for generating the proper divisors of the first 20,000 integers; at the expense of simplicity.
<lang 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 __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]))</lang>
{{out}}
<pre>[{1}, {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}, {1, 3}, {1, 2, 5}]
15120 79</pre>
| |||