Tworzenie listy dzielników w Haskell

Question

Mam problem 21 w eulerproject. Jedna część wymaga znalezienia listy właściwych dzielników liczby. tj. tam, gdzie pozostała liczba: n i pewna liczba mniej niż n. Więc zrobiłem tego Haskella, ale GHCI wpada w złość na mnie.

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

Problem polega na tym, że nie wiem jak zrobić:

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

tak, że tylko zwraca liczbę mniejszą niż n które dzielą równo na n.

Answer 1

Potrzebujesz tylko oddzielnej zmiennej.

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] 

Teraz, jeśli chcesz, aby nieco bardziej wydajne, już wiemy, że dzielnik nie będzie więcej niż połowę n i wiemy, 1 jest dzielnikiem wszystkiego. I chodźmy naprzód i uczynić go nieco więcej Haskell-y do rozruchu, unikanie wyrażeń listowych:

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

Jeśli kolejność na liście dzielników nie jest ważne, można zrobić to znacznie bardziej skuteczne tylko przez sprawdzanie dzielników w zakresie [2..sqrt n].

Coś jak to (prawdopodobnie można by było zrobić kilka lokalnych optymalizacje, jeśli myślał o tym więcej):

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

Gdzie dzielników jest poprzednią realizację i dzielniki jest nowe:

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

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

UWAGA: Użyliśmy nub, aby usunąć wszelkie powtórzenia, podczas gdy w rzeczywistości jedynym możliwym powtórzeniem byłoby ograniczenie, jeśli n jest liczbą kwadratową. Możesz uczynić go nieco bardziej wydajnym, lepiej radząc sobie z tą sprawą, ale uważam, że jest to bardziej czytelne (jeśli czas pracy nie jest krytyczny).