1

私はプロジェクトオイラーで質問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これをintのリストに変換する方法と組み合わせると、

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

考えられるすべての因子の素因数分解が必要ですが、関数は1つの素因数分解のみを返すようです。

于 2009-12-06T16:01:21.347 に答える