Re: [Haskell-cafe] Zumkeller numbers

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 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" 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe