[Haskell-cafe] Looking for suggestions to improve my algorithm
chaddai.fouche at gmail.com
Sun Sep 2 05:55:23 EDT 2007
Right, your program is 2 times faster than mine on my machine... I
wonder if there is a better structure to do this bookkeeping than
IntSet (maybe Sequence slightly remanied ?), anyway it goes to show
how sometimes the bookkeeping can be more expensive than the
operations it's meant to prevent !
As for my sumOfProperDivisors function it's dead simple, I would even
say stupid (but it's faster than anything else I tried for now).
An accumArray use the function you give it to update a cell, ok ? Here
it's just (+) and all cells began their life as 1 since 1 is a proper
divisors of all numbers (except 1, thus the (1,-1) for correctness).
The following list just associate each proper divisor of a num with
it, so the final value of a cell is the sum of those proper divisors.
To achieve that we make factor take the value of all proper divisors
possible for numbers from 1 to 1000000, in other words [2..1000000
`div` 2] (the `div` 2 is ok since we're speaking about proper divisors
here), and then we go on to associate this divisor with all the
numbers he divides properly, which are [factor * 2, factor *
Is it clear now ?
More information about the Haskell-Cafe