Составление списка делителей в Haskell

Я делаю задачу 21 в eulerproject. Одна часть требует найти список правильных делителей числа. то есть там, где есть остаток n и некоторое число меньше, чем n. Поэтому я сделал этот Haskell, но GHCI рассердился на меня.

Проблема в том, что я не знаю, как это сделать:

так что он возвращает число меньше n, которое равномерно делит на n.

Ответы

Ответ 1

Вам просто нужна отдельная переменная.

Prelude> let divisors n = [x | x <- [1..(n-1)], n `rem` x == 0]
Prelude> divisors 20
[1,2,4,5,10]
Prelude> divisors 30
[1,2,3,5,6,10,15]

Теперь, если вы хотите сделать его более эффективным, мы уже знаем, что делитель не будет больше половины n, и мы знаем, что 1 является делителем всего. И, давайте продолжим и сделаем немного больше Haskell-y для загрузки, избегая понимания списка:

Prelude> let divisors n = 1 : filter ((==0) . rem n) [2 .. n `div` 2]
Prelude> divisors 20
[1,2,4,5,10]
Prelude> divisors 30
[1,2,3,5,6,10,15]
Prelude> divisors 31
[1]

Ответ 2

Если порядок списка делителей не важен, вы можете сделать это значительно более эффективным, только проверяя делители в диапазоне [2..sqrt n].

Что-то вроде этого (возможно, вы могли бы сделать некоторые локальные оптимизации, если бы подумали об этом больше):

divisors' n = (1:) $ nub $ concat [ [x, div n x] | x <- [2..limit], rem n x == 0 ]
     where limit = (floor.sqrt.fromIntegral) n

Где divisors - предыдущая реализация, а divisors - новая:

*Main> (sum.divisors) 10000000
14902280
(4.24 secs, 521136312 bytes)

*Main> (sum.divisors') 10000000
14902280
(0.02 secs, 1625620 bytes)

Примечание: Мы использовали nub для удаления любых повторений, когда на самом деле единственным возможным повторением было бы ограничение, если n - квадратное число. Вы можете сделать его несколько более эффективным, если обработать этот случай лучше, но я считаю, что этот способ более читабельен (если время работы не критично).