# 99 questions/Solutions/31

(Difference between revisions)

(**) Determine whether a given integer number is prime.

Solution 1

```isPrime :: Integral a => a -> Bool
isPrime p = p > 1 &&
(all ((/= 0).(p `rem`)) \$ candidateFactors p)

candidateFactors p = takeWhile ((<= p).(^2)) [2..]```

Well, a natural number p is a prime number if it is larger than 1 and no natural number n >= 2 with n^2 <= p is a divisor of p. That's exactly what is implemented: we take the list of all integral numbers starting with 2 as long as their square is at most p and check that for all these n there is a non-zero remainder concerning the division of p by n.

However, we don't actually need to check all natural numbers <= sqrt P. We need only check the primes <= sqrt P:

```candidateFactors p = let z = floor \$ sqrt \$ fromIntegral p + 1 in
takeWhile (<= z) primesTME```

This uses

```{-# OPTIONS_GHC -O2 -fno-cse #-}
-- tree-merging Eratosthenes sieve
--  producing infinite list of all prime numbers
primesTME = 2 : gaps 3 (join [[p*p,p*p+2*p..] | p <- primes'])
where
primes' = 3 : gaps 5 (join [[p*p,p*p+2*p..] | p <- primes'])
join  ((x:xs):t)        = x : union xs (join (pairs t))
pairs ((x:xs):ys:t)     = (x : union xs ys) : pairs t
gaps k xs@(x:t) | k==x  = gaps (k+2) t
| True  = k : gaps (k+2) xs```
The tree-merging Eratosthenes sieve here seems to strike a good balance between efficiency and brevity, and semi-standard `union` function is readily available from
Data.List.Ordered
package, put here just for reference. More at Prime numbers haskellwiki page.
```-- duplicates-removing union of two ordered increasing lists
union (x:xs) (y:ys) = case (compare x y) of
LT -> x : union  xs  (y:ys)
EQ -> x : union  xs     ys
GT -> y : union (x:xs)  ys```

Solution 2

The following is faster (in Hugs, Nov 2002 version):

```isPrime n = n > 1 &&
foldr (\p r -> p*p > n || n `rem` p /= 0 && r)
True primesTME```
This reuses same `primesTME` list on subsequent invocations, but the
(takeWhile ...)
list in the first solution seems to be recreated anew for each call to `isPrime` (i.e. it may or may not be eliminated by a compiler, while the second solution explicitly uses the same `primesTME` list so there's no problem to begin with).