Before we finish off this chapter, how about a final example? I was thinking we could write a function to generate a list of prime numbers up to a limit. We've already seen the code for this so let's make it a function and, to keep it interesting, let's optimize it a bit.
It turns out that you don't need to divide it by all numbers from 2 to N-1 to decide if a number N is prime. You can stop at . Moreover, you don't need to test the division for all numbers from 2 to , you can just use the primes in that range. I'll leave it to you to figure out why this works, if you're interested. Let's 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 = int(ceil(sqrt(candidate))) # division limit for prime in primelist: # we try only the primes if prime > root: # no need to check any further break if candidate % prime == 0: is_prime = False break if is_prime: primelist.append(candidate) return primelist
The code is the same as in the previous chapter. We have changed the division algorithm so that we only test divisibility using the previously calculated primes and we stopped once the testing divisor was greater than the root of the candidate. We used the result list primelist
to get the primes for the division. We calculated the root value using a fancy formula, the integer value of the ceiling of the root of the candidate. While a simple int(k ** 0.5) + 1
would have served our purpose as well, the formula I chose is cleaner and requires me to use a couple of imports, which I wanted to show you. Check out the functions in the math
module, they are very interesting!