Найти число из диапазона 1.1000, у которого сумма делителей максимальна

@Catstail · Регистрация: 12.02.2012

Студворк — интернет-сервис помощи студентам

Задача из раздела "C для начинающих".

Вот мое решение (довольно громоздкое):

Haskell

task n = search z 0 0 0
         where search [] _ p _ = p+1
               search (s:ss) k p m | (s>m) = search ss (k+1) k s
                                   | otherwise = search ss (k+1) p m                
               z=map (\ x -> foldl (\ acc y -> if (x `mod` y)==0 then acc+y else acc) 0 [2..x `div` 2]) [1..n]

XRuZzz · 24.06.2017, 13:13

Соберу здесь ссылки на всякий случай:

Кликните здесь для просмотра всего текста

Найти натуральное число от 1 до 10000 с максимальной суммой делителей -- ссылка на исходную тему
Найти число с максимальной суммой делителей
Найти натуральное число с максимальной суммой делителей

Haskell

1	maxSumDiv n = foldl1 max [(y, x) \| x <- [1..n], y <- [sum [t \| t <- [1..x], mod x t == 0]]]

Сумма находится в fst, ответ в snd.

Немного потестировал на ideone, при n = 10000:
Код на C: Найти число с максимальной суммой делителей
Оптимизированный код С - time: 0 memory: 9432
Медленный код C - time: 0.43 memory: 16256
Код на C: Найти натуральное число от 1 до 10000 с максимальной суммой делителей
time: 0.06 memory: 10320
Код Catstail - time: 0.88 memory: 8388607
Моё решение - time: 1.56 memory: 8388607

При n = 100000, уложился в limit(видимо он составляет 5 сек) только оптимизированный код на C, который показал время 0.03.

Опции темы