[Haskell-cafe] Zumkeller numbers
Richard O'Keefe
ok at cs.otago.ac.nz
Tue Dec 8 17:19:17 EST 2009
On Dec 9, 2009, at 1:15 AM, Daniel Fischer wrote:
> Am Dienstag 08 Dezember 2009 08:44:52 schrieb Ketil Malde:
>> "Richard O'Keefe" <ok at cs.otago.ac.nz> writes:
>>> factors n = [m | m <- [1..n], mod n m == 0]
>>
>> -- saves about 10% time, seems to give the same result:
>> factors n = [m | m <- [1..n `div` 2], mod n m == 0]++[n]
>
> Even faster (for large enough n):
>
> factors n =
> mergeAll [if q == d then [d] else [d, q] | d <- [1 .. isqrt n]
> , let (q,r) = n `divMod`
> d, r == 0]
We can improve on that somewhat:
factors 1 = [1]
factors n = 1 : candidates 2 4 n [n]
where candidates d d2 n hi =
if d2 < n then
let (q,r) = divMod n d in
if r == 0 then d : candidates (d+1) (d2+d+d+1) n (q:hi)
else candidates (d+1) (d2+d+d+1) n hi
else if d2 == n then d:hi else hi
This never constructs a cons cell it doesn't mean to keep.
>
More information about the Haskell-Cafe
mailing list