Question: **This is a spoiler to task #3 of Project Euler! Don't continue to read, if you want to solve it by yourself.**

I am trying to learn Haskell by writing programs for Project Euler. At the moment I'm trying to solve task #3 which asks for the largest prime factor of the number 600851475143.

To do this, I create a list `liste` which contains all numbers, which are divisors of this number (up to its squareroot). My strategy is now, to count the divisors of these numbers, to decide, if they are prime.

```
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]

```

The result, which should appear here, should be a list containing 8 lists with the divisors of the elements of `liste`. Instead, the list

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

```

is printed.

How is this behaviour to be explained?

Answer: 
The Problem is the type declaration `primelist :: Int -> [Int]`. It forces Haskell to use native integers, i.e. 32-Bit integers on a 32-Bit platform. However, if you leave it out, Haskell will infer the function type to be `Integer -> [Integer]`. Integers allow computations with arbitrary precision, but are a little bit slower than native types. 

To quote from "[What's the difference between Integer and Int"](http://www.haskell.org/haskellwiki/FAQ#What.27s_the_difference_between_Integer_and_Int.3F) in the Haskell FAQ:

> 
> Operations on Int can be much faster than operations on Integer, but
>  overflow and underflow **can cause weird bugs**.
> 
> 
> 

Now isn't that the truth.
I am not sure if this will help you, but I also am working through Project Euler to help teach myself Haskell, and I devised the following solution:

```
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

```

Here, `defacto` de-factors a prime out of a number, so `defacto 2 12` returns 4 and `defacto 5 14` returns 14. `gpf` is a function to find the greatest prime factor, though it requires a list of primes up to `x` to be in scope. The key component is `prim`, which either returns 1 if the number is smaller than the next prime, returns the first prime in its prime list if x is a perfect power of that prime (i.e. if all other primes smaller than p have been factored out of x), and otherwise performs a recursive call on the defactored x and the truncated prime list. This has the effect of continuously shrinking x while linearly traversing the prime list, so that we need not test any primes that cannot factor into x, and we don't need to keep retesting the same primes on the reduced value of x. Hope this helps you.