[Haskell-cafe] Zumkeller numbers

Lennart Augustsson lennart at augustsson.net
Tue Dec 8 18:02:30 EST 2009


And if you use quotRem it's faster (unless you're running on some
exotic hardware like NS32K).

On Tue, Dec 8, 2009 at 10:19 PM, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:
>
> 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.
>
>>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>


More information about the Haskell-Cafe mailing list