Project euler problem 3 in haskell

I'm new in Haskell and try to solve 3 problem from http://projecteuler.net/.

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

What is the largest prime factor of the number 600851475143 ?

My solution:

import Data.L开发者_JS百科ist

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

I try to run for example:

getD 13195
> 29

But when i try:

getD 600851475143

I get error Exception: Prelude.maximum: empty list Why?

Thank you @Barry Brown, I think i must use:

getD :: Integer -> Integer

But i get error:

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

Thank you.

---

Your type signature limits the integer values to about 2^29. Try changing Int to Integer.

Edit:

I see that you already realised that you need to use Integer instead of Int. You need to change the types of both getD and isSimpleNumber otherwise you will get a type mismatch.

Also in general, if you are having trouble with types, simply remove the type declarations and let Haskell tell you the correct types.

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

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

---

After you found the error, may I point out that your solution is quite verbose? In this case a very simple implementation using brute force is good enough:

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)  

---

this question is easy enough for brute-force solution, but it is a bad idea to do so because the whole idea of project euler is problems you need to really think of to solve (see end of answer) so here are some of your program's flaws:

first, use rem instead of mod. it is more efficient.

some mathematical thinking should have told you that you don't need to check all numbers from 1 to x in the isprime function and the getD function, but checking all numbers from the squareroot to one (or reversed) should be sufficient. note that in getD you will actually need to filter numbers between x and the square root, because you search for the biggest one.

why do you use the maximum function in getD? you know the list is monotonically growing, so you may as well get the last one.

despite you only need the biggest divisor (which is prime) you compute the divisors list from small to big making the computer check for each value if it is a divisor or not although discarding the result once a bigger divisor is found. it should be fixed by filtering the list of numbers from x to 1, not from 1 to x. this will cause the computer to check divisibility (how should I say that?) for the biggest possible divisor, not throwing to the trash the knowledge of previous checks. note that this optimization takes effect only if the previous point is optimized, because otherwise the computer will compute all divisors anyway.

with the previous points mixed, you should have filtered all numbers [x,x-1 .. squareroot x] and taken the first.

you don't use an efficient isPrime function. if I were you, I would have searched for an isprime library function, which is guaranteed to be efficient. and there are more..

with this kind of code you will never be able to solve harder project euler problems. they are designed to need extra thinking about the problem (for instance noticing you don't have to check numbers greater from the square root) and writing fast and efficient code. this is the purpose of project euler; being smart about programming. so don't skip it.