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] > > (But checking against primes is even faster, it seems) That's peanuts, the important part is to partition smaller numbers (i.e. (sigma(n)-2*n) vs. sigma(n)). Still faster would be using the fact that if n is Zumkeller and gcd n m = 1, then n*m is Zumkeller, too. > > -k _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe