Finding Prime Numbers
=====================

.. note:: :doc:`This is a literate Haskell page: you can load it directly into
   ghci by following these steps <haskell_literate>`.


Finding Primes
--------------

In this program we're going to write a couple of functions for finding prime
numbers. The functions we write won't be extremely efficient, but they are a
good example how to write useful Haskell_ functions.

Recall that an integer :math:`n` is **prime** if it's greater than 1, and is
evenly divisible only by 1 and itself. For example, 2 is the smallest prime
(and the only even prime), and the next few primes are 3, 5, 7, 11, and 13.
`There are an infinite number of primes
<https://en.wikipedia.org/wiki/Euclid%27s_theorem>`_, and in general `it is
quite challenging to efficiently determine if a large numbers are prime
<https://en.wikipedia.org/wiki/Primality_test>`_ or not.

It's not hard to see that if the smallest divisor of :math:`n`, that's greater
than 1, is :math:`n` itself, then :math:`n` must be prime. For example, the
smallest divisor (greater than 1) of 101 is 101, so 101 is prime.

So we can write this function::

> smallest_divisor :: Integer -> Integer
> smallest_divisor n 
>     | n < 0     = error "n must be >= 0"
>     | n == 0    = 0
>     | n == 1    = 1
>     | otherwise = head (dropWhile (\x -> n `mod` x /= 0) [2..n])

The ``dropWhile`` function takes two parameters: a function, and a list. Here
we've passed it the lambda function ``(\x -> n `mod` x /= 0)``, which returns
``True`` just when ``x`` does *not* evenly divide ``n``. The expression
``[2..n]`` returns the list of integers from 2 to n, i.e. ``[2, 3, ..., n-1,
n]``. It's the list of all possible divisors of ``n``. The call to
``dropWhile`` checks the elements of ``[2..n]``, in order one at a time
(starting with 2), and removes the value if it doesn't divide evenly into
n. The first element of the list that is returned is thus the smallest divisor
of n.

Now it's easy to write ``is_prime``::

> is_prime :: Integer -> Bool
> is_prime n | n < 2     = False
>            | otherwise = (smallest_divisor n) == n

We can then use this to write ``is_composite``:: 

> is_composite :: Integer -> Bool
> is_composite n | n <= 1     = False
>                | otherwise  = not (is_prime n)

A composite number is an integer greater than 1 that is not prime.

Suppose you want a list of all the primes up to 100::

    filter is_prime [2..100]

Or a list of all the composites up to 100::

    filter is_composite [2..100]

You could also write these as functions::

> primes_less_than :: Integer -> [Integer]
> primes_less_than n = filter is_prime [2..(n-1)]
>
> composites_less_than :: Integer -> [Integer]
> composites_less_than n = filter is_composite [2..(n-1)]

If you want to calculate the first 100 primes, or composites, you could do
this::

    take 100 (filter is_prime [2..])

    take 100 (filter is_composite [2..])

The expression ``[2..]`` is an *infinite* list ``[2,3,4,5,...]``. Since
Haskell_ uses lazy evaluation, it doesn't generate any elements on ``[2..]``
until they are needed, and so in the expression ``take 100 (filter is_prime
[2..])`` only a finite portion of ``[2..]`` ends up getting evaluated.