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

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