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