Proper divisors: Difference between revisions
Content added Content deleted
(→{{header|Haskell}}: Added a definition of properDivisors in terms of primeFactors) |
m (→Python: Functional: Slightly simpler definition) |
||
| Line 3,939: | Line 3,939: | ||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
<lang python>'''Proper divisors''' |
<lang python>'''Proper divisors''' |
||
from itertools import accumulate, chain, groupby, product |
from itertools import accumulate, chain, groupby, product |
||
from functools import reduce |
from functools import reduce |
||
from math import floor, sqrt |
from math import floor, sqrt |
||
# properDivisors :: Int -> [Int] |
# properDivisors :: Int -> [Int] |
||
def properDivisors(n): |
def properDivisors(n): |
||
'''The ordered divisors of n, excluding n itself. |
'''The ordered divisors of n, excluding n itself. |
||
''' |
''' |
||
def go(a, |
def go(a, x): |
||
(i, e) = ie |
|||
return [a * b for a, b in product( |
return [a * b for a, b in product( |
||
a, |
a, |
||
accumulate( |
accumulate( |
||
chain([1], |
chain([1], x), |
||
lambda a, |
lambda a, b: a * b |
||
) |
) |
||
)] |
)] |
||
return sorted( |
return sorted( |
||
reduce(go, [ |
reduce(go, [ |
||
( |
list(g) for _, g in groupby(primeFactors(n)) |
||
[list(g) for _, g in groupby(primeFactors(n))] |
|||
], [1]) |
], [1]) |
||
)[:-1] if 1 < n else [] |
)[:-1] if 1 < n else [] |
||
# --------------------------TEST--------------------------- |
# --------------------------TEST--------------------------- |
||
# main :: IO () |
# main :: IO () |
||
def main(): |
def main(): |
||
'''Tests''' |
'''Tests''' |
||
print( |
print( |
||
fTable('Proper divisors of [1..10]:')(str)(str)( |
fTable('Proper divisors of [1..10]:')(str)(str)( |
||
| Line 3,976: | Line 3,974: | ||
)(range(1, 1 + 10)) |
)(range(1, 1 + 10)) |
||
) |
) |
||
print('\nExample of maximum divisor count in the range [1..20000]:') |
print('\nExample of maximum divisor count in the range [1..20000]:') |
||
print( |
print( |
||
| Line 3,984: | Line 3,982: | ||
) |
) |
||
) |
) |
||
# -------------------------DISPLAY------------------------- |
# -------------------------DISPLAY------------------------- |
||
# fTable :: String -> (a -> String) -> |
# fTable :: String -> (a -> String) -> |
||
# (b -> String) -> (a -> b) -> [a] -> String |
# (b -> String) -> (a -> b) -> [a] -> String |
||
| Line 4,004: | Line 4,002: | ||
xShow, fxShow, f, xs |
xShow, fxShow, f, xs |
||
) |
) |
||
# -------------------------GENERIC------------------------- |
# -------------------------GENERIC------------------------- |
||
# primeFactors :: Int -> [Int] |
# primeFactors :: Int -> [Int] |
||
def primeFactors(n): |
def primeFactors(n): |
||
| Line 4,016: | Line 4,014: | ||
r = qr[1] |
r = qr[1] |
||
return step(r), 1 + r |
return step(r), 1 + r |
||
def step(x): |
def step(x): |
||
return 1 + (x << 2) - ((x >> 1) << 1) |
return 1 + (x << 2) - ((x >> 1) << 1) |
||
def go(x): |
def go(x): |
||
root = floor(sqrt(x)) |
root = floor(sqrt(x)) |
||
def p(qr): |
def p(qr): |
||
q = qr[0] |
q = qr[0] |
||
return root < q or 0 == (x % q) |
return root < q or 0 == (x % q) |
||
q = until(p)(f)( |
q = until(p)(f)( |
||
(2 if 0 == x % 2 else 3, 1) |
(2 if 0 == x % 2 else 3, 1) |
||
)[0] |
)[0] |
||
return [x] if q > root else [q] + go(x // q) |
return [x] if q > root else [q] + go(x // q) |
||
return go(n) |
return go(n) |
||
# snd :: (a, b) -> b |
# snd :: (a, b) -> b |
||
def snd(tpl): |
def snd(tpl): |
||
'''Second member of a pair.''' |
'''Second member of a pair.''' |
||
return tpl[1] |
return tpl[1] |
||
# until :: (a -> Bool) -> (a -> a) -> a -> a |
# until :: (a -> Bool) -> (a -> a) -> a -> a |
||
def until(p): |
def until(p): |
||
| Line 4,052: | Line 4,050: | ||
return v |
return v |
||
return lambda f: lambda x: go(f, x) |
return lambda f: lambda x: go(f, x) |
||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||