There are quite a few optimizations you could do:
- Like user2357.. suggested in the comments, test palindromeness first, and then check if the number is prime, since prime check is more expensive.
- You don't need to check even number divisibility once you check is the number is divisible by 2. So you can change it to
[2] + range(3, int(n**0.5) + 1, 2)
to check only odd numbers after 2. (Also you need to do sqrt + 1 like I mentioned in the comments) - You should use
()
instead of[]
.[]
generates the entire list of factors first and only then checks forany
. If you use()
, it creates a generator, so it stops as soon as aTrue
value is found without calculating the entire list. - You should also use
xrange
instead ofrange
for the same reason (xrange
gives a generator,range
gives a list) - You can use the Sieve of Eratosthenes algorithm to significantly reduce the time taken for prime number check.
- You can also see if the palindrome check can be made faster. You can actually skip a whole lot of numbers instead of doing just
+ 1
each time.
Here is a version with most of these optimizations except the last two:
def next_higher(n):
if n % 2 == 0:
n = n - 1
while True:
n = n + 2
s = str(n)
if s == s[::-1]:
if not any((n % i == 0 for i in xrange(3, int(n**0.5) + 1, 2))):
return n
This should be pretty fast for your needs I believe. But you can do the last 2 optimizations to make it much more faster if you want.