Project Euler, Problem #7, Haskell

-- By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we
-- can see that the 6th prime is 13. What is the 10 001st prime
-- number?


-- Solution #1: a basic one

main :: IO ()
main =
  print $
  [x | x <- [1 ..], null [y | y <- [2 .. div x 2], mod x y == 0]] !! 10001


-- 104743


-- real 0m40,243s
-- user 0m39,956s
-- sys  0m0,248s

-- #################################
-- Solution #2: still basic, but faster


-- The idea behind this solution is that, if a number can't be divided
-- by any prime number smaller than itself, then this number is prime
-- itself. The checked number "cn" is checked against the list of prime
-- numbers "pl". If the number is prime, it's added to the list; if
-- it's not, then it's incremented and checked again. The list is
-- expanded as long as its size is less than 10001; when the length of
-- the list is equal to 10001 its last item is returned.


-- pcc (prime checker concatenator) definition #1: if an auxiliary
-- copy of the list of primes is empty, which means that the checked
-- number is prime, then the number is added to the main list of
-- primes and then the number is incremented.

pcc :: Integral t => [t] -> [t] -> t -> t
pcc pl [] cn = lsc (pl ++ [cn]) (cn + 1)


-- pcc definition #2: the checked number is recursively checked
-- against numbers in an auxiliary copy of the list of prime numbers;
-- the numbers on the list go in ascending order, so smaller, thus
-- more likely divisors are checked first.

pcc pl (x:xs) cn =
  if mod cn x == 0
    then pcc pl pl (cn + 1)
    else pcc pl xs cn


-- lsc (list size checker) definition: the length of the main list is
-- checked: if it's equal to 10001, then the last item of the main
-- list of prime numbers is returned, otherwise incrementation, check
-- and list expansion continue.

lsc :: Integral t => [t] -> t -> t
lsc pl cn =
  if length pl < 10001
    then pcc pl pl cn
    else last pl

main :: IO ()
main = print $ lsc [2] 3

-- 104743

-- real 0m15,728s
-- user 0m15,596s
-- sys  0m0,077s