# 99 questions/Solutions/31

### From HaskellWiki

Line 3: | Line 3: | ||

<haskell> | <haskell> | ||

isPrime :: Integral a => a -> Bool | isPrime :: Integral a => a -> Bool | ||

− | isPrime p = p > 1 && (all (\n -> p `mod` n /= 0 ) $ takeWhile (\n -> n*n <= p) [2..]) | + | isPrime p = p > 1 && |

+ | (all (\n -> p `mod` n /= 0 ) | ||

+ | $ takeWhile (\n -> n*n <= p) [2..]) | ||

</haskell> | </haskell> | ||

− | Well, a natural number p is a prime number iff it is larger than 1 and no natural number n with n >= 2 and 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 remainder concerning the division of p by n. | + | Well, a natural number ''p'' is a prime number iff it is larger than '''1''' and no natural number ''n'' with ''n >= 2'' and ''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 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 | + | However, we don't actually need to check all natural numbers <= sqrt P. We need only check the natural ''primes'' <= sqrt P. |

<haskell> | <haskell> |

## Revision as of 20:29, 30 May 2011

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

isPrime :: Integral a => a -> Bool isPrime p = p > 1 && (all (\n -> p `mod` n /= 0 ) $ takeWhile (\n -> n*n <= p) [2..])

Well, a natural number *p* is a prime number iff it is larger than **1** and no natural number *n* with *n >= 2* and *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 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 natural *primes* <= sqrt P.

-- Infinite list of all prime numbers allPrimes :: [Int] allPrimes = filter (isPrime) [2..] isPrime :: Int -> Bool isPrime p | p < 2 = error "Number too small" | p == 2 = True | p > 2 = all (\n -> p `mod` n /= 0) (getPrimes sqrtp) where getPrimes z = takeWhile (<= z) allPrimes sqrtp = floor . sqrt $ fromIntegral p

Note that the mutual dependency of allPrimes and isPrime would result in an infinite loop if we weren't careful. But since we limit our observation of allPrimes to <= sqrt x, we avoid infinite recursion.

While the mutual dependency is interesting, this second version is not necessarily more efficient than the first. Though we avoid checking all natural numbers <= sqrt P in the isPrime method, we instead check the primality of all natural numbers <= sqrt P in the allPrimes definition.