CODEWITHSUNDEEP
haskellrecursionprimes
germainelol
germainelol

Reputation: 3331

Check whether an integer (or all elements of a list of integers) be prime

I'm doing a simple Haskell function using recursion. At the moment, this seems to work but, if I enter 2, it actually comes up as false, which is irritating. I don't think the code is as good as it could be, so, if you have any advice there, that'd be cool too!

I'm pretty new to this language!

EDIT: Ok, so I understand what a prime number is.

For example, I want to be able to check 2, 3, 5, 7, etc and have isPrime return true. And of course if I run the function using 1, 4, 6, 8 etc then it will return false.

So, my thinking is that in pseudo code I would need to do as follows:

num = 2 -> return true
num > 2 && num = even -> return false

After that, I'm struggling to write it down in any working code so the code below is my work in process, but I really suck with Haskell so I'm going nowhere at the minute.

module Recursion where

isPrime :: Int -> Bool
isPrime x = if x > 2 then ((x `mod` (x-1)) /= 0) && not (isPrime (x-1)) else False

Upvotes: 2

Views: 2259

Answers (3)

jub0bs
jub0bs

Reputation: 66214

Here are two facts about prime numbers.

  1. The first prime number is 2.
  2. An integer larger than 2 is prime iff it's not divisible by any prime number up to its square root.

This knowledge should naturally lead you to something like the following approach:

-- primes : the infinite list of prime numbers
primes :: [Integer]
primes = 2 : filter isPrime [3,5..]

-- isPrime n : is positive integer 'n' a prime number?
isPrime :: Integer -> Bool
isPrime n
    | n < 2     = False
    | otherwise = all (\p -> n `mod` p /= 0) (primesPrefix n)
    where primesPrefix n = takeWhile (\p -> p * p <= n) primes

As a bonus, here is a function to test whether all items of a list of integers be prime numbers.

-- arePrimes ns : are all integers in list 'ns' prime numbers?
arePrimes :: [Integer] -> Bool
arePrimes = all isPrime

Some examples in ghci:

ghci> isPrime 3
True
ghci> isPrime 99
False
ghci> arePrimes [2,3,7]
True
ghci> arePrimes [2,3,4,7]
False

Upvotes: 3

Will Ness
Will Ness

Reputation: 71070

You can get a recursive formulation from the "2 divisors" variant by step-wise refinement:

isPrime n 
    = 2 == length  [ d | d <- [1..n], rem n d == 0 ]
    = n > 1 && null [ d | d <- [2..n-1], rem n d == 0 ]
    = n > 1 && and [ rem n d > 0 | d <- takeWhile ((<= n).(^2)) [2..] ]
    = n > 1 && g 2
       where
         g d = d^2 > n || (rem n d > 0 && g (d+1))
    = n == 2 || (n > 2 && rem n 2 > 0 && g 3)
       where
         g d = d^2 > n || (rem n d > 0 && g (d+2))

And that's your recursive function. Convince yourself of each step's validity.

Of course after we've checked the division by 2, there's no need to try dividing by 4,6,8, etc.; that's the reason for the last transformation, to check by odds only. But really we need to check the divisibility by primes only.

Upvotes: 0

Random Dev
Random Dev

Reputation: 52270

Ok,

let's do this step by step:

In math a (natural) number n is prime if it has exactly 2 divisors: 1 and itself (mind 1 is not a prime).

So let's first get all of the divisors of a number:

divisors :: Integer -> [Integer]
divisors n = [ d | d <- [1..n], n `mod` d == 0 ]

then get the count of them:

divisorCount :: Integer -> Int
divisorCount = length . divisors

and voila we have the most naive implementation using just the definition:

isPrime :: Integer -> Bool
isPrime n = divisorCount n == 2

now of course there can be quite some impprovements:

  • instead check that there is no divisor > 1 and < n
  • you don't have to check all divisors up to n-1, it's enough to check to the squareroot of n
  • ...

Ok just to give a bit more performant version and make @Jubobs happy ;) here is an alternative:

isPrime :: Integer -> Bool
isPrime n
  | n <= 1 = False
  | otherwise = not . any divides $ [2..sqrtN]
  where divides d = n `mod` d == 0
        sqrtN = floor . sqrt $ fromIntegral n

This one will check that there is no divisor between 2 and the squareroot of the number

complete code:

using quickcheck to make sure the two definitions are ok:

module Prime where

import Test.QuickCheck

divisors :: Integer -> [Integer]
divisors n = [ d | d <- [1..n], n `mod` d == 0 ]

divisorCount :: Integer -> Int
divisorCount = length . divisors

isPrime :: Integer -> Bool
isPrime n
  | n <= 1 = False
  | otherwise = not . any divides $ [2..sqrtN]
  where divides d = n `mod` d == 0
        sqrtN = floor . sqrt $ fromIntegral n

isPrime' :: Integer -> Bool
isPrime' n = divisorCount n == 2

main :: IO()
main = quickCheck (\n -> isPrime' n == isPrime n)

!!warning!!

I just saw (had something in the back of my mind), that the way I did sqrtN is not the best way to do it - sorry for that. I think for the examples with small numbers here it will be no problem, but maybe you really want to use something like this (right from the link):

(^!) :: Num a => a -> Int -> a
(^!) x n = x^n

squareRoot :: Integer -> Integer
squareRoot 0 = 0
squareRoot 1 = 1
squareRoot n =
   let twopows = iterate (^!2) 2
       (lowerRoot, lowerN) =
          last $ takeWhile ((n>=) . snd) $ zip (1:twopows) twopows
       newtonStep x = div (x + div n x) 2
       iters = iterate newtonStep (squareRoot (div n lowerN) * lowerRoot)
       isRoot r  =  r^!2 <= n && n < (r+1)^!2
   in  head $ dropWhile (not . isRoot) iters

but this seems a bit heavy for the question on hand so I just remark it here.

Upvotes: 7

Related Questions