Haskell での因数分解メソッドの実装

Question

私がやっている 質問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?

Answer 1

いくつかのコードゴルフのために私は非常に簡単です素敵電力設定機能を書いています。

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

このアルゴリズムの欠点は、あなたがそれを望むようにそれを見ていないので、それはあなたのために完全であるが、元のセットを、含まれていないということです。

intのリストにあなたの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)],
   ...
]

すべての可能な要因の素因数分解が必要ですが、機能は一つだけ素因数分解を返すように思われます。