I am doing question 266 at Project Euler and after a bit of searching, found this method of quickly finding the factors of a number. What you do is find all the permutations of the prime factors of a number: these are its factors.
I already have a module to find the prime power factors of a number, eg:
Main> primePowerFactors 196
[(2,2),(7,2)]
This is basically showing that: 2^2 * 7^2 == 196. From here I want to find all the permutations of those powers, to give the factors of 196 thusly:
I came up with the following:
factors n = [a|a<-map facs (primePowerFactors n), y <- [0..(snd $ last $ primePowerFactors n)]]
where
facs (x,y) = (x,y)
rSq n = toInteger $ round $ sqrt (fromInteger n)
psr n = last $ dropWhile (<= rSq n) $ factors n
p = foldl' (*) 1 $ takeWhile (< 190) primes
answer = (psr p) `mod` (10^16)
But my problem is that factors doesn't work properly. I want it to permute through all the possible values of the exponent for each prime factor and then find the product to give the factor. How can it be modified to return the just the factors of n?
for some code golf i wrote a nice power set function that is pretty simple.
powerSet [] = []
powerSet (x:xs) = xs : map (x:) (powerSet xs) ++ (powerSet xs)
A deficiency of this algorithm is that it doesn't include the original set, however that is perfect for you since it doesn't look like you want it.
combine this with a way to convert your primePowerFactors n into a list of ints, lets say
ppfToList = concatMap (\(x,y)->replicate y x)
using these helpers, a list of factors from a number n is generated with
factors n = nub . map product . powerSet . ppfToList . primePowerFactors $ n
-- will be out of order, you can add a call to `sort` to fix that
This sort of algorithm is probably a bit harder to express in terms of a list comprehension.