Lập danh sách các ước số trong Haskell

Question

Tôi đang làm vấn đề 21 trong eulerproject. Một phần yêu cầu tìm danh sách các ước số thích hợp của một số. nghĩa là phần còn lại của n và một số ít hơn n. Vì vậy, tôi đã thực hiện điều này Haskell, nhưng GHCI tức giận với tôi.

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

Vấn đề là tôi không biết làm thế nào để thực hiện:

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

để nó chỉ trả về số thấp hơn n mà chia đều thành n.

Answer 1

Bạn chỉ cần một biến riêng biệt.

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] 

Bây giờ, nếu bạn muốn làm cho nó hiệu quả hơn một chút, chúng ta đã biết rằng một ước sẽ không có nhiều hơn một nửa số n, và chúng tôi biết 1 là ước của tất cả mọi thứ. Và, chúng ta hãy đi trước và làm cho nó thêm một chút Haskell-y để khởi động, tránh một danh sách hiểu:

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

Nếu thứ tự của danh sách các ước là không quan trọng, bạn có thể làm cho điều này đáng kể hiệu quả hơn bằng cách chỉ kiểm tra ước trong phạm vi [2..sqrt n].

Something như thế này (bạn có thể có thể làm cho một số optimisations địa phương nếu bạn nghĩ về nó nhiều hơn):

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

đâu ước là việc thực hiện trước đó, và ước là mới:

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

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

LƯU Ý: Chúng tôi đã sử dụng nub để loại bỏ bất kỳ sự lặp lại nào, khi trên thực tế, sự lặp lại duy nhất có thể là giới hạn, nếu n là số vuông. Bạn có thể làm cho nó hiệu quả hơn một chút bằng cách xử lý trường hợp này tốt hơn, nhưng tôi thấy cách này dễ đọc hơn (nếu thời gian chạy không quan trọng).