在Haskell中列出除数列表

Question

我在eulerproject做了问题21.一部分需要找到一个数字的适当除数列表.即有剩余部分n和少数部分的数量n.所以我做了这个Haskell,但GHCI对我很生气.

divisors n =[ n | n <- [1..(n-1)], n `rem` [1..(n-1)] ==0 ]

问题是我不知道如何制作:

n `rem` [1..(n-1)]

所以它只返回小于n该分数的数字n.

Answer 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]

Answer 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

除数是先前的实现,除数是新的:

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

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

注意: 我们使用nub来删除任何重复,实际上唯一可能的重复是限制,如果n是平方数.通过更好地处理这种情况,你可以使它更有效率,但我发现这种方式更具可读性(如果运行时间不重要).