3

これはプロジェクト オイラーのタスク #3 のネタバレです! 自分で解決したい場合は、読み続けないでください。

Project Euler のプログラムを作成して Haskell を学ぼうとしています。現時点では、番号 600851475143 の最大の素因数を要求するタスク #3 を解決しようとしています。

listeこれを行うには、この数の約数 (平方根まで) であるすべての数を含むリストを作成します。私の戦略は、これらの数の約数を数え、それらが素数かどうかを判断することです。

number = 600851475143
-- sn = sqrt number
sn = 775146

liste = [x | x <- [1..sn],  (mod number x == 0)]
-- liste = [1,71,839,1471,6857,59569,104441,486847]

primelist :: Int -> [Int]
primelist z = [y | y <- [1..z], mod z y == 0] 

main = print [primelist x | x <- liste]

ここに表示される結果は、 の要素の除数を持つ 8 つのリストを含むリストになりますliste。代わりに、リスト

[[1],[1,3],[1,29],[1,3,29,87]]

印刷されます。

この振る舞いはどのように説明されるべきですか？

4

2 に答える 2

6

問題は型宣言primelist :: Int -> [Int]です。Haskell にネイティブ整数、つまり 32 ビット プラットフォームでは 32 ビット整数を使用するように強制します。ただし、省略した場合、Haskell は関数の型が であると推測しますInteger -> [Integer]。整数は任意の精度で計算できますが、ネイティブ型より少し遅くなります。

Haskell FAQ の「整数と整数の違いは何ですか」から引用するには:

Int の操作は Integer の操作よりもはるかに高速ですが、オーバーフローとアンダーフローによって奇妙なバグが発生する可能性があります。

今、それは真実ではありません。

于 2013-06-01T22:24:18.993 に答える
0

これが役に立つかどうかはわかりませんが、Haskell を独学するために Project Euler にも取り組んでおり、次の解決策を考案しました。

defacto :: Integer -> Integer -> Integer
defacto x p | x == p = 1
            | x`mod`p==0 = defacto (x`div`p) p
            | otherwise = x

gpf :: Integer -> Integer
gpf = \x -> prim (x,primes)

prim :: (Integer,[Integer]) -> Integer
prim (x,(p:ps)) | p > x = 1
                | (defacto x p) == 1 = p
                | otherwise = prim((defacto x p),ps)

n :: Integer
n = 600851475143

ここでdefactoは、数値から素数を素因数分解するため、defacto 2 124 をdefacto 5 14返し、14を返します。gpfは最大の素因数を見つける関数ですxが、範囲内にするには素数のリストが必要です。キー コンポーネントはprimで、数値が次の素数よりも小さい場合は 1 を返し、x がその素数の完全べき乗である場合 (つまり、p より小さい他のすべての素数が因数分解されている場合) は、素数リストの最初の素数を返します。 x)、それ以外の場合は、デファクタリングされた x と切り捨てられた素数リストに対して再帰呼び出しを実行します。これには、素数リストを線形にトラバースしながら x を継続的に縮小する効果があるため、x に因数分解できない素数をテストする必要はなく、x の縮小値で同じ素数を再テストし続ける必要もありません。これがお役に立てば幸いです。

于 2014-05-13T22:48:29.370 に答える