haskell中的項目euler問題3

我是Haskell的新手，嘗試從http://projecteuler.net/解決3個問題。haskell中的項目euler問題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

我得到錯誤例外：前奏曲。最大值：空列表爲什麼？

謝謝@Barry布朗，我想我必須使用：

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

謝謝。

來源

2011-07-01 0xAX

哪個版本的Haskell？也就是說，你在使用哪種環境？有些不支持任意精度整數。 –

我使用ghc-7.0.3 – 0xAX

任意精度整數實際上是Haskell語言的一部分，所以不是這樣。沒有Haskell實現可以忽略它們。 –

您的類型簽名將整數值限制爲大約2^29。嘗試將Int更改爲Integer。

編輯：

我看你已經意識到，你需要使用整數，而不是詮釋。你需要改變getD和isSimpleNumber的類型，否則你會得到一個類型不匹配。另外一般情況下，如果您遇到類型問題，只需刪除類型聲明並讓Haskell告訴您正確的類型。

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

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

來源

2011-07-01 07:04:28

「如果您遇到類型問題，只需刪除類型聲明，然後讓Haskell告訴您正確的類型」 - 對於Haskell的新手來說，這真的是一個糟糕的建議。我認爲在學習Haskell時最好手工編寫所有類型。爲了更好地理解類型系統。 – aindl

搞清楚你自己的類型*是理想的，但這不是OP在這裏做的。讓GHC告訴你這個類型比在StackOverflow上告訴你的人更有教育意義。 –

我目前正在嘗試這個問題，並正在這樣做......但它似乎沒有工作。任何想法爲什麼？ – tibbon

當您發現錯誤後，我是否可以指出您的解決方案非常冗長？在這種情況下使用蠻力一個非常簡單的實現是不夠好：

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)

來源

2011-07-01 07:34:06 Landei

使用'f'做非功能會傷害我的大腦。 –

我用它作爲「因素」。我傾向於使用'fn'來完成自己的功能，但我同意'd'會更好。 – Landei

這個問題是蠻力解決方案很容易，但它是一個壞主意，這樣做是因爲項目歐拉的整體思路是問題你需要真正想到解決（見答案的結尾）所以這裏有一些你的程序的缺陷：

首先，用rem代替mod。它更有效率。

一些數學思想應該告訴你，你不需要檢查isprime函數和getD函數中從1到x的所有數字，但檢查從squareroot到one（或reverse）的所有數字應該是足夠的。請注意，在getD中，實際上需要過濾x和平方根之間的數字，因爲您要搜索最大的數字。

爲什麼在getD中使用最大函數？你知道這份名單是單調增長的，所以你最好還是得到最後一份。

儘管您只需要最大的除數（這是總理），但您可以計算除數列表，從小到大使得計算機檢查每個值是否爲除數，儘管一旦找到更大的除數就會丟棄結果。它應該通過過濾從x到1的數字列表來解決，而不是從1到x。這將導致計算機檢查可分性（我應該怎麼說？）爲最大可能的除數，而不是向垃圾桶投擲先前檢查的知識。請注意，只有前一點被優化時，此優化纔會生效，否則計算機將無論如何計算所有除數。

與前面的點混合在一起，你應該已經過濾了所有的數字[x，x-1..squareroot x]並且取第一個。

您不使用有效的isPrime函數。如果我是你，我會搜索isprime庫函數，這是保證高效。和更多..

用這種代碼你永遠無法解決更難的項目歐拉問題。它們被設計爲需要對問題進行額外的思考（例如注意到您不必檢查平方根以上的數字）並編寫快速有效的代碼。這是項目歐盟的目的;在編程方面很聰明。所以不要跳過它。

來源

2014-02-19 20:42:09 user3329719

haskell中的項目euler問題3

回答

相關問題