制作Haskell中的除数列表

您只需要一个单独的变量。

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

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..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)

注: