题
我在做 问题 266 在 Project Euler 并经过一番搜索后,发现 这个方法 快速找出一个数的因数。你要做的就是找到一个数的质因数的所有排列:这些都是它的因素。
我已经有一个模块可以查找数字的素功率因数,例如:
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?
解决方案
对于一些高尔夫代码,我编写了一个非常简单的很好的幂集函数。
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
这种算法用列表理解来表达可能有点困难。
其他提示
首先, 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)],
...
]
需要对所有可能的因子进行素因数分解,但该函数似乎只返回一个素因数分解。
不隶属于 StackOverflow