Other than the few things pointed out above, it might be 'cleaner' to use a helper function to test primality. For example:
import math
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:
return my_primes
if is_prime(i, my_primes):
my_primes.append(i)
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):
my_primes.append(i)
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.
True
andFalse
, not'true'
and'false
'. And usenot prime
andand prime
. \$\endgroup\$ – Ry- Jul 16 '13 at 4:08