Other than the few things pointed out above, it might be 'cleaner' to use a helper function to test primality. For example:
def is_prime(x, primes):
return all(x % i for i in primes if i < math.sqrt(x))
def first_k_primes(i, k, my_primes):
if k <= 0:
if is_prime(i, my_primes):
return first_k_primes(i + 2, k - 1, my_primes)
return first_k_primes(i + 2, k, my_primes)
print(first_k_primes(5, 10, [2, 3]))
Now, I know you didn't want any "fancy-pants" coding, but this is actually really really similar to your iterative approach, just using recursion. If we look at each bit we have the following:
is_prime(x, primes): this tests whether the value
x is prime or not. Just like in your code, it takes the modulo of
x against all of the primes up to the square root of
x. This isn't too tricky :) The
all() function gathers all of these tests and returns a boolean (True or False). If all of the test (from 2 up to sqrt(x)) are False (i.e., every single test confirms ti is prime) then it returns this finding, and we know x is prime.
first_k_primes(i, k, my_primes): ok, this is recursive, but it isn't too tricky. It takes 3 parameters:
- i: the number to test
- k: the number of primes you still need to find until you have the
number you want, e.g. if you want the first 4 primes, and you
already know [2, 3, 5], then k will be 1
- my_primes: which is the list of primes so far.
In python, the first thing you need to do with a recursive function, is to figure out a base case. Here, we want to keep going until we have k number of primes (or until k = 0), so that is our base case.
Then we test to see if
i is prime or not. If it is, we add it to our growing list of my_primes. Then, we go to the next value to test (
i += 2), we can reduce k by one (since we just added a new prime) and we continue to grow our list of my_primes by calling the modified:
first_k_primes(i + 2, k - 1, my_primes).
Finally, if it happens that
i is not prime, we don't want to add anything to
my_primes and all we want to do is test the next value of
i. This is what the last return statement does. It will only get this far if we still want more primes (i.e. k is not 0) or i wasn't prime.
Why do I think this is more readable? The main thing is that I think it is good practice to separate out your logic.
is_prime() does one thing and one thing only, and it does the very thing it says it does - it tests a value. Similarly
first_k_primes() does exactly what it says it does too, it returns the first k primes. The really nice thing, is that this all boils down to one simple test:
if is_prime(i, my_primes):
the rest just sets up the boundaries (i.e. the kth limit). So once you have seen a bit of recursion, you intuitively zoom in on the important lines and sort of 'ignore' the rest :)
As a side note, there is a slight gotcha with using recursion in Python: Python has a recursion limit of 1,000 calls. So if you need to recurse on large numbers it will often fail. I love recursion, it is quite an elegant way to do things. But it might also be just as easy to do the
first_k_primes() function as an iterative function, or using a generator.