Prime number generator

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 …

Advertisements

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 ...
This entry was posted in haskell and tagged , , , . Bookmark the permalink.

One Response to Prime number generator

  1. 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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s