One final example

Before we finish off this chapter, let us go through one last example. We could write a function to generate a list of prime numbers up to a limit; we have already seen the code for this in Chapter 3, Conditionals and Iteration, so let us make it a function and, to keep it interesting, let us optimize it a bit.

First of all, we do not need to divide by all the numbers from 2 to N-1 to decide whether a number, N, is prime. We can stop at √N (the square root of N). Moreover, we do not need to test the division for all the numbers from 2 to √N, as we can just use the primes in that range. We leave it up to you to figure out the math for why this works, if you are interested.

Let us see how the code changes:

# primes.py
from math import sqrt, ceil
def get_primes(n):
    """Calculate a list of primes up to n (included)."""
    primelist = []
    for candidate in range(2, n + 1):
        is_prime = True
        root...