project euler Problem 3

pe3.hs

num = 600851475143
nums = reverse [1..600851475143]

isPrime :: (Integral a) => a -> Bool
isPrime x = (product $ map (mod x) [2..(x-1)]) /= 0

getPrimes :: (Integral a) => [a] -> [a]
getPrimes xs = filter isPrime $ xs

primes = getPrimes nums

isFactor :: (Integral a) => a -> a -> Bool
isFactor x y = (mod x y) == 0

largestPrimeFactor = find (isFactor num) $ primes

the problem:

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

What is the largest prime factor of the number 600851475143 ?

Beacuse you reverse the the list [1..600851475143] , the runtime system has to build up the entire reversed list before processing.

Your isPrime is slow too, because * of Int and Integer is not a short-circuit operator, and product is implemented using *.

And this is my attemp, imperative and ugly.

largest n
    | isPrime n = n
    | otherwise = largest' n 1 1
  where
    largest' n x m
        | n < x * x = m
        | n `rem` x == 0 && isPrime x = largest' n (x + 1) x
        | otherwise = largest' n (x + 1) m

Thanks. This function works with small numbers. But for 600851475143 I got "memory allocation failed".

You shuold modify your isPrime too.
Here is mine:

isPrime 2 = True
isPrime n = and [ n `rem` x /= 0 | x <- [2.. ceiling $ sqrt $ fromIntegral n]]

$ time ./Prime 
6857

real    0m0.049s
user    0m0.043s
sys 0m0.003s

thanks! "and" is short-circuit and use sqrt to reduce n to sqrt(n). this works.