empty list on recursive function

Question

Im trying do some work on Project Euler for fun, but I got stuck now on an problem and want to move on but cant seem to get my function working. Im trying to get count the primefactors of a given integer. The function works on smaller numbers such as 13195:

> primeFactor 13195
[29,13,7,5]

But when I run a bigger number such as 600851475143:

> primeFactor 601851475143
[]

This seems really weird to me. I know haskell is a lazy language, but I don´t think it should be that lazy...

primeFactor' :: Int -> [Int]
primeFactor' n = [ p | p <- primes' [] [2 .. n], n `mod` p == 0 ]
   where primes' :: [Int] -> [Int] -> [Int]
         primes' ys [] = ys
         primes' ys (x:xs) | x `notMultipleOf` ys = primes' (x:ys) xs
                           | otherwise            = primes' ys xs                                                                                         

-- helper function to primeFactor'
notMultipleOf :: Int -> [Int] -> Bool
notMultipleOf n [] = True
notMultipleOf n xs = and [n `mod` x /= 0 | x <- xs]

josejuan · Accepted Answer · 2013-12-20 10:16:04Z

2

Int has 32 bits you can't store that number (use Integer).

On the other hand, you can use Data.Numbers.Primes (and see code):

> primeFactors 601851475143
[3,3,23,1009,2881561]
> primeFactors 600851475143
[71,839,1471,6857]

answered Dec 20, 2013 at 10:16

josejuan

9,60628 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Chris Taylor · Accepted Answer · 2013-12-20 10:22:43Z

2

It's an integer overflow error. The Int type can only represent numbers up to 2^31 - 1

>> maxBound :: Int
2147483647

The number you entered overflows --

>> 601851465143 :: Int
556043703

On the other hand, if you use the Integer type there is no overflow --

>> 601851465143 :: Integer
601851465143

answered Dec 20, 2013 at 10:22

Chris Taylor

47.6k15 gold badges113 silver badges156 bronze badges

Comments

jamshidh · Accepted Answer · 2013-12-20 10:40:20Z

1

Honestly, I don't know why you obtained an empty list.... or anything at all.

You are using a brute force method to find a list of primes, dividing all numbers by all smaller primes than it. This scales like n^2.

How long should this take to complete?

N^2 ~= (601851475143)^2 ~= 10^22 operations

It is a bit better than this, because the density of primes drops, but not much.... Let's shave off a factor of 10^2 to account for this. On a modern 8 core 4GHz machine (assuming 1cpu cycle per operation.... way optimistic), this should take

10^20 operations / (10^10 operation/sec) = 10^10 sec ~= 300 years

to complete.

You might want to look for a new algorithm.

answered Dec 20, 2013 at 10:40

jamshidh

12.1k21 silver badges31 bronze badges

Collectives™ on Stack Overflow

empty list on recursive function

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related