First, some comments on your code:
return d.append(b)
is not very nice. You would think this function actually returns something, but this just returns None
. Instead you modify a list being passed in as a parameter. This is a very C thing to do. Instead, just return the boolean value and use it to build a list using a list comprehension:
d = [x for x in b if isprime(x)]
Note that this now no longer solves the problem. That is because your naming should be improved. The isprime
function does not actually check if a number is prime. It does that somewhere in its implementation, but that is not what it really does. I would rename the function to something like nearest_prime
. You should also try to avoid single letter variable names. A few exceptions like integers called i
might exist, but not too many.
You also generally want to avoid writing recursive functions in Python. Python has a maximum recursion limit, it does not do tail call optimization. Instead make your function iterative.
Python has an official style-guide, PEP8. It recommends using spaces around =
when using it for assignment.
You should always add a docstring to your functions.
This part of the answer assumes that you want what is written in your title, and not what is written in the question. The number you want is the next larger prime, unless the number is prime itself.
In any case, you can greatly speed up your code by pre-computing the primes. This will be only really worth it if you query enough numbers.
For getting lots of prime numbers fast, you want to use a prime sieve. Here is the most simple one, the Sieve of Eratosthenes:
def prime_sieve(limit):
"""Generator that yields all prime number up to `limit`."""
prime = [True] * limit
prime[0] = prime[1] = False
for i, is_prime in enumerate(prime):
if is_prime:
yield i
for n in range(i * i, limit, i):
prime[n] = False
The hard part is then knowing up to which number to get the primes. I'm going to ignore this and just use a large enough number (since I know all numbers you are going to test). In your code you might want to automate finding that number.
For finding the next bigger prime, or the number itself, we just have to look in the list of primes until we either find our number or a number that is bigger than our number. We could do a linear search for it, but it will be faster to do a binary search (since the primes are already sorted). For this you can use the bisect
module, which is in the standard library:
from bisect import bisect_left
def nearest_prime(x, primes):
"""Find the first prime number from `primes` greater or equal to `x`."""
return primes[bisect_left(primes, x)]
And that's really already it. Just add your calling code under a if __name__ == "__main__":
guard to allow importing from this module without the example code being run and you're done:
if __name__ == "__main__":
primes = list(prime_sieve(100))
numbers = [89, 54, 36, 74, 44, 19, 12]
nearest_primes = [nearest_prime(x, primes) for x in numbers]
print(nearest_primes)
# [89, 59, 37, 79, 47, 19, 13]
On my machine, your code takes 0.00015s, while this takes 0.00004s. But as I said, this will be even faster the more numbers you check.
If you really do mean the nearest prime (so it can also be smaller), it takes only one extra step, we also need to check the prime number before the index we get:
def nearest_prime(x, primes):
"""Find the closest prime number to `x` in `primes`."""
i = bisect_left(primes, x)
return min(primes[i - 1], primes[i], key=lambda y: abs(x - y))