Get primes below x

Question

I'm trying to write a procedure that returns a list of all primes below a given number.

For example:

Prelude>primes 8  
[2,3,5,7]  

When I try to load the file I get Parse error in pattern Failed, modules loaded: none. If someone could point me in the right direction I would be grateful.

primes :: Int -> [Int]
primes x < 2 = []
primes x | isPrime x == True = primes (x - 1) ++ x
         | otherwise = primes (x - 1)

isPrime :: Int -> Bool
isPrime x | x < 2 = False
          | x == 2 || x == 3 = True
          | divEven x == True = False
          | divOdd x 3 == True = False
          | otherwise = True

divEven :: Int -> Bool
divEven x | mod x 2 == 0 = True
          | otherwise = False

divOdd :: Int Int -> Bool
divOdd x num | mod x num == 0 == True
             | num <= x/2 = divOdd x (num + 2)
             | otherwise = False

Answer 1

A collection of small mistakes.

1. Your syntax is incorrect.

   primes x < 2 = []
   

   Probably you meant

   primes x | x < 2 = []
   

   Similarly, where you write

   divOdd x num | mod x num == 0 == True
   

   you probably meant

   divOdd x num | mod x num == 0 = True
   

2. The type signature

   divOdd :: Int Int -> Bool
   

   is not valid. You probably meant

   divOdd :: Int -> Int -> Bool
   

3. x is of type Int, and (/) :: Fractional a => a -> a -> a cannot be applied to it. You probably mean num <= x `div` 2 or 2 * num <= x.

   divOdd :: Int Int -> Bool
   divOdd x num | mod x num == 0 == True
                | num <= x/2 = divOdd x (num + 2)
                | otherwise = False
   

4. x is of type Int, not [Int]. (++) :: [a] -> [a] -> [a] will not apply to it.

   primes x | isPrime x == True = primes (x - 1) ++ x
   

   Perhaps you meant

   primes x | isPrime x == True = primes (x - 1) ++ [x]
   

Finally, this is a fairly inefficient way of generating primes. Have you considered a sieve? Prime numbers - HaskellWiki may be a bit difficult for you right now, but shows many different strategies.

Answer 2

Here's a re-write of your functions using list comprehensions (also in Wikipedia), perhaps this is more visually apparent:

primes :: Int -> [Int]
primes x | x<2  = [] 
         | x<4  = [2..x]
         | True = primes (x-1) ++ [x | isPrime x]

your isPrime is

isPrime x = x > 1 && 
          ( x < 4 || 
            and [ rem x n /= 0 | n <- 2 : [3,5..(div x 2)+2] ] )

and is a function defined in standard Prelude. It will test entries in a list, left to right, to see if all are True. It will stop on the first False entry encountered, so the rest of them won't get explored.

Sometimes when the code is more visually apparent it is easier to see how to improve it.