製作Haskell中的除數列表

我在eulerproject中做問題21。其中一部分需要找到一個數字的正確除數列表。即其餘部分是n以及少於n的部分數目。所以我做了這個Haskell，但是GHCI對我很生氣。製作Haskell中的除數列表

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

的問題是，我不知道該怎麼做：

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

所以它只返回比n是整除到n少的數量。

來源

2009-09-26 Jonno_FTW

你只需要一個單獨的變量。現在

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是一切的約數。而且，讓我們繼續前進，使更多的哈斯克爾-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]

來源

2009-09-26 07:00:59

爲什麼列表理解不是很Haskell？此外，一個小問題，有沒有辦法找到列表中所有列表的總和？ – 2009-09-26 18:18:49

我不是Haskell的老手，但我沒有真正看到任何Haskell庫中使用的列表解析。小回答：'sum $ map sum x'，例如'sum $ map sum [[1,2,3]，[4,5,6]，[7,8,9]]'產生45.' – 2009-09-26 19:37:42

或者'總和。 concat'，它首先製作一個大名單。 – 2011-06-04 00:44:02

如果除數列表的順序並不重要，可以讓這個顯著更多的唯一有效檢查範圍[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)

注：我們我用的凸起，以消除任何重複的時候，其實是唯一可能的重複將是極限，如果n是一個平方數。通過更好地處理這種情況，可以使它更有效一些，但我發現這種方式更具可讀性（如果運行時間不重要）。

來源

2012-08-16 09:38:51 Greg

製作Haskell中的除數列表

回答

相關問題