CODEWITHSUNDEEP
haskellcastingtype-conversion
Mark Karavan
Mark Karavan

Reputation: 2674

Rounding a float to an int in haskell

Problem 3 of Project Euler says: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

I made a lazy list of primes, then I do a takeWhile they are less than the square root of 600851475143, and test each prime to see if it is a factor.

primes :: [Integer]
primes = sieve [2..]
    where
        sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
primeFactors :: Integer -> Integer
primeFactors x = last $ filter (\y -> x `mod` y == 0) $ takeWhile (< floor (sqrt x)) $ primes

However, I get an error with (< floor (sqrt x)):

projecteuler.hs:34:70:
    No instance for (RealFrac Integer) arising from a use of `floor'
    Possible fix: add an instance declaration for (RealFrac Integer)
    In the second argument of `(<)', namely `floor (sqrt x)'
    In the first argument of `takeWhile', namely `(< floor (sqrt x))'
    In the expression: takeWhile (< floor (sqrt x))

projecteuler.hs:34:77:
    No instance for (Floating Integer) arising from a use of `sqrt'
    Possible fix: add an instance declaration for (Floating Integer)
    In the first argument of `floor', namely `(sqrt x)'
    In the second argument of `(<)', namely `floor (sqrt x)'
    In the first argument of `takeWhile', namely `(< floor (sqrt x))'

This is weird: :t floor gives me (Integral b, RealFrac a) => a -> b, which means that this floor should be returning a integer. How can I add an instance declaration (or do whatever is necessary to fix this?)

Also, any suggestions on code optimization are greatly appreciated :)

Edit: this has been solved, and now I am cleaning it up. I've encapsulated everything inside of the main function, so it looks like this:

p003primeFactors :: Integer -> [Integer]
p003primeFactors x = filter (\y -> x `mod` y == 0) $ takeWhile (\p -> p^2 <= x) $ primes
    where
        primes :: [Integer]
        primes = sieve [2..]
            where
                sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]

Is this the best way to create namespaces for functions like this?

Upvotes: 1

Views: 725

Answers (1)

kosmikus
kosmikus

Reputation: 19637

The actual problem is the second error. (The first is just a consequence.) The x is an Integer, so you cannot call sqrt on it, because that requires a Floating instance.

Try:

takeWhile (< floor (sqrt (fromIntegral x)))

This will convert x from an integer to a floating point number so that sqrt can operate on it.

Upvotes: 3

Related Questions