Problem 7: Primes

Bernard: What if the Prime Minister insists we help them?

Humphrey: Then we follow the four-stage strategy...

A prime number is a number that can only be divided by itself and 1 without remainders. A classic algorithm to obtain prime numbers is the sieve method, which is performed as follows:

1. We start from 2, as 1 is not a prime number
2. Take the smallest number p (initially 2), p must be a prime number
3. Sieve out all the numbers that can be divided by p, these cannot be primes
4. Goto step 1

Hint: You may want to use filter and recursion.

def starting_from(start):
    """Yields natural numbers starting from start.

    >>> sf = starting_from(0)
    >>> [next(sf) for _ in range(10)] == list(range(10))
    True
    """
    "*** YOUR CODE HERE ***"


def sieve(t):
    """Suppose the smallest number from t is p, sieves out all the
    numbers that can be divided by p (except p itself) and recursively
    sieves out all the multiples of the next smallest number from the
    reset of of the sequence.

    >>> list(sieve(iter([3, 4, 5, 6, 7, 8, 9])))
    [3, 4, 5, 7]
    >>> list(sieve(iter([2, 3, 4, 5, 6, 7, 8])))
    [2, 3, 5, 7]
    >>> list(sieve(iter([1, 2, 3, 4, 5])))
    [1]
    """
    "*** YOUR CODE HERE ***"


def primes():
    """Yields all the prime numbers.

    >>> p = primes()
    >>> [next(p) for _ in range(10)]
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    """
    "*** YOUR CODE HERE ***"