プロジェクトオイラー問題3 in haskell

Question

私はHaskellで新しく、http://projecteuler.net/から3つの問題を解決しようとしています。

The prime factors of 13195 are 5, 7, 13 and 29. 

What is the largest prime factor of the number 600851475143 ? 

私のソリューション：

import Data.List 

getD :: Int -> Int 
getD x = 
    -- find deviders 
    let deriveList = filter (\y -> (x `mod` y) == 0) [1 .. x] 
     filteredList = filter isSimpleNumber deriveList 
    in maximum filteredList 

-- Check is nmber simple 
isSimpleNumber :: Int -> Bool 
isSimpleNumber x = let deriveList = map (\y -> (x `mod` y)) [1 .. x] 
         filterLength = length (filter (\z -> z == 0) deriveList) 
         in 
          case filterLength of 
          2 -> True 
          _ -> False 

は、私は、たとえば実行しよう：

getD 13195 
> 29 

しかし、私は試してみてください。

getD 600851475143 

私はエラー例外を取得：前奏曲を。最大：空リストなぜですか？

getD :: Integer -> Integer 

しかし、私はエラーを取得：

Couldn't match expected type `Int' with actual type `Integer' 
Expected type: [Int] 
    Actual type: [Integer] 
In the second argument of `filter', namely `deriveList' 
In the expression: filter isSimpleNumber deriveList 

はありがとう

は@Barryブラウンは、私は私が使用しなければならないと思います、ありがとうございました。

Answer 1

タイプシグネチャは、整数値を約2^29に制限します。 IntをIntegerに変更してください。

編集：

私はあなたがすでにあなたが整数の代わりのIntを使用する必要があることに気づいていることがわかります。 getDとisSimpleNumberの両方の型を変更する必要があります。そうしないと型の不一致が発生します。

また、一般的に、型に問題がある場合は、型宣言を削除し、Haskellに正しい型を伝えるようにしてください。

Main> :t getD 
getD :: Integral a => a -> a 

Main> :t isSimpleNumber 
isSimpleNumber :: Integral a => a -> Bool 

Answer 2

エラーを見つけたら、あなたの解決策は非常に冗長であることを指摘してもいいですか？この場合、ブルートフォースを使用して非常に単純な実装は十分です：

getD n = getD' n 2 where 
    getD' n f | n == f = f 
      | n `mod` f == 0 = getD' (n `div` f) f 
      | otherwise = getD' n (succ f) 

Answer 3

この質問は、ブルートフォースソリューションのために十分に簡単ですが、プロジェクトのオイラーの全体的なアイデアが問題であるため、これを行うには悪い考えですあなたは本当に解決することを考える必要があります（答えの終わりを参照してください） あなたのプログラムの欠陥のいくつかはここにあります：

最初に、modの代わりにremを使用してください。より効率的です。

isprime関数とgetD関数で1からxまでのすべての数値をチェックする必要はないと言わざるを得ないが、平方根からすべての数を1に（または逆に）チェックするだけで十分である。 getDでは、xと平方根の間の数値をフィルタリングする必要があることに注意してください。なぜなら、最大のものを検索するからです。

なぜgetDで最大限の機能を使用しますか？あなたはリストが単調に成長していることを知っているので、最後のものを得ることもできます。

最大の除数（小数点以下）が必要なにもかかわらず、より大きな除数が見つかると結果を破棄しますが、除数であればコンピュータが各値をチェックするように、小数から大への除数リストを計算します。 1からxまでではなく、xから1までの数値のリストをフィルタリングすることで修正する必要があります。これは、コンピュータに可能な最大の除数についての除算をチェックさせ（以前のチェックの知識をゴミ箱に投げ込まない）。この最適化は、前の点が最適化されている場合にのみ有効になります。そうしないと、コンピュータはすべての除数を計算します。

前の点が混在している場合は、すべての数値[x、x-1 .. squareroot x]をフィルタリングして最初のものを取ったはずです。

あなたは効率的なisPrime関数を使用しません。もし私があなただったら、効率的であることが保証されているisprimeライブラリ関数を探していたでしょう。 などがあります。

この種のコードでは、プロジェクトのユーラー問題を解決することはできません。 （例えば、平方根より大きな数をチェックする必要がないことに気付くなど）問題についての余分な考えが必要であり、高速かつ効率的なコードを書くように設計されています。これはプロジェクトオイラーの目的です。プログラミングに精通している。だからそれをスキップしないでください。