在Haskell中实现因式分解法

Question

我在做项目Euler中的question 266，经过一番搜索之后，发现this method很快找到了数字的因素。你所做的是找到一个数字的主要因素的所有排列：这些是它的因素。

我已经有一个模块，找了好几个的主要动力因素，如：

Main> primePowerFactors 196 
[(2,2),(7,2)] 

这基本上表明：2^2 * 7^2 == 196。在这里，我想找到这些权力的所有排列，给予196正是如此的因素：

• （2^0）（7^0）= 1
• （2^1）（7^0）= 2
• （2^2）（7^0）= 4
• （2^0）（7^1）= 7
• （2^1）（7^1）= 14
• （2^2）（7^1）= 28
• （2^0）（7^2）= 49
• （2^1）（7^2）= 98

我想出了以下内容：

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) 

但我的问题是，factors不能正常工作。我希望它通过每个主要因素的指数的所有可能值进行置换，然后找到产品给出该因子。如何修改以返回n的因子？

Answer 1

对于某些代码高尔夫球我写了一个很好的功率设置功能，很简单。

powerSet [] = [] 
powerSet (x:xs) = xs : map (x:) (powerSet xs) ++ (powerSet xs) 

此算法的不足之处在于它不包含原始集合，但对于您来说，这看起来并不像您想要的那样完美。

一种方法结合起来给你的primePowerFactors n转换成整数的列表，让使用这些帮手，是由许多因素的清单说

ppfToList = concatMap (\(x,y)->replicate y x) 

n与

factors n = nub . map product . powerSet . ppfToList . primePowerFactors $ n 
-- will be out of order, you can add a call to `sort` to fix that 

产生这种算法在列表理解方面可能有点难以表达。

Answer 2

首先，facs是身份的功能：

facs (x,y) = (x,y) 

的y在左侧的模式匹配，必然，而你可能是为了它是从列表中理解的y。在列表理解中绑定的变量名称是本地理解的，不能在where子句的不同范围内使用。

此外，在列表理解的y只从最后的因素指数计算：

y <- [0..(snd $ last $ primePowerFactors n)] 

每个因子它自己的指数应该考虑，而不仅仅是总是最后一个因素的指数。

一个更根本的问题是，该factors函数的返回类型似乎并不匹配它的意图：

*Euler> :t factors 
factors :: Integer -> [(Integer, Int)] 

这将返回的主要因素权力清单，同时它应该产生的列表这些构造如下：

[ 
    [(2,0), (7,0)], 
    [(2,1), (7,0)], 
    [(2,2), (7,0)], 
    [(2,0), (7,1)], 
    [(2,1), (7,1)], 
    ... 
] 

需要所有可能因素的素因式分解，但函数似乎只返回一个素因式分解。