1

我在 Project Euler 做第266 题，经过一番搜索，找到了这种快速查找数字因数的方法。你要做的是找到一个数的质因数的所有排列：这些就是它的因数。

我已经有一个模块来查找数字的主要功率因数，例如：

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的因子？

4

2 回答 2

2

对于一些代码高尔夫，我编写了一个非常简单的不错的功率设置函数。

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

就列表理解而言，这种算法可能更难表达。

于 2009-12-07T07:54:15.760 回答
1

首先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)],
   ...
]

需要对所有可能因素进行素数分解，但该函数似乎只返回一个素数分解。

于 2009-12-06T16:01:21.347 回答