Machen Sie eine Liste der Teiler in Haskell

Ich Tue problem 21 in eulerproject.
Ein Teil erfordert das finden der Liste der ordnungsgemäße Teiler einer Zahl. also wo ist Rest n und eine Anzahl von weniger als n. Also machte ich diese Haskell, aber GHCI wird wütend auf mich.

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

Das problem ist, dass ich nicht wissen, wie zu machen:

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

so, es gibt nur die Nummer weniger als n teilen gleichmäßig in n.

InformationsquelleAutor Jonno_FTW | 2009-09-26
  1. 18

    Brauchen Sie nur eine separate variable.

    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]

    Nun, wenn Sie wollten, um es ein bisschen mehr effizient, wir wissen schon, dass der divisor nicht mehr als die Hälfte der n, und wir wissen, 1 ist ein Teiler von allem. Und, lassen Sie uns gehen Sie vor und machen es ein bisschen mehr Haskell-y zu starten, die Vermeidung einer list comprehension:

    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]
    • Warum ist die Liste Verständnis nicht sehr Haskell? Auch, eine kleine Frage, gibt es eine Möglichkeit zu finden, die Summe der Summe aller Listen in einer Liste?
    • Ich bin nicht eine Haskell-veteran, mit allen Mitteln, aber ich habe nicht wirklich gesehen, jede Liste Verstehens in beliebiger Haskell-Bibliotheken, zum Beispiel. Kleine Antwort: sum $ map sum x wie sum $ map sum [ [1,2,3], [4,5,6], [7,8,9] ] was in der 45.
    • Oder sum . concat, die erste macht eine große Liste.
    InformationsquelleAutor Mark Rushakoff
  2. 7

    Wenn die Reihenfolge der Liste der Teiler ist nicht wichtig, machen Sie dies deutlich effizienter werden, indem nur die überprüfung Teiler im Bereich [2..sqrt n].

    Etwas wie dieses (Sie könnten wahrscheinlich machen einige lokale Optimierungen, wenn Sie sich Gedanken über es mehr):

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

    Wo Teiler der bisherigen Umsetzung und der Teiler " ist die neue:

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

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

    HINWEIS:
    Wir ich verwendet nub zu entfernen, keine Wiederholungen, wenn in der Tat die einzig mögliche Wiederholung wäre limit, wenn n ein Quadrat. Man könnte ihn etwas effizienter Umgang mit diesem Fall besser, aber ich finde, dieser Weg ist besser lesbar (wenn die Laufzeit nicht entscheidend ist).

    InformationsquelleAutor Greg
Schreibe einen Kommentar