Someone ask for a function that generates the prime numbers between two limits [1 and N given by the user], but he forgot to specify the time execution.

I write this first function in haskell:

module Main where
main :: IO()
main = interact function
function :: String -> String
function = unlines . map show . concat . map process . lines
process :: String -> [Integer]
process snum = let num = toInt snum
in [i | i <- filter isPrime [2..(num-1)] ]
isPrime :: Integer -> Bool
isPrime n = and $ map (\i -> n `mod` i /= 0) [2..(n-1)]
toInt :: String -> Integer
toInt = read

The input to try is a list of natural numbers contained in a file.

If we try with 100000 it will take:

real 0m36.796s

user 0m36.521s

sys 0m0.167s

Trying with another version of isPrime:

isPrime :: Integer -> Bool
isPrime n = (==) [] $ filter (\i -> mod n i == 0) [2..floor (n'/log n')]
where n' = fromInteger n

Now, there is a big diference!!

real 0m4.647s

user 0m4.556s

sys 0m0.033s

Trying another function for isPrime:

isPrime :: Integer -> Bool
isPrime n = (==) [] $ dropWhile (\i -> mod n i /= 0) [2..floor (n' / log n')]
where n' = fromInteger n

But his time is the same, even sometimes is more.

I think the last should take less time, because dropWhile not always walk all the list, but filter always walk all the list. I don’t understand what’s happening.

Trying with another function for isPrime:

isPrime :: Integer -> Bool
isPrime n = (==) [] $ dropWhile (\i -> mod n i /= 0) [2..floor (sqrt n')]
where n' = fromInteger n

This version has a direfferent rank: *sqrt n*, and his time execution is also less:

real 0m0.492s

user 0m0.457s

sys 0m0.033s

Ok, i will return in another lazy time …

### Like this:

Like Loading...

## About gcarlos

Some people call me engineer, other developer or programmer, but I rather like be called scientist because that is what I really want to do ...

I was suggested this blog by my cousin. I’m

not sure whether this post is written by him as no one else know such detailed about my difficulty.

You are amazing! Thanks!