The challenge is to find and print the largest palindrome prime under 1000.def reverse(integer):    result = 0    while (integer != 0):        result *= 10        result += (integer % 10)        integer //= 10    return resultdef is_palindromic(integer):    return integer == reverse(integer)def produce_sieve(limit):    sieve = [True] * limit    sieve_length = len(sieve)    for prime in range(2, sieve_length):        if (sieve[prime]):            for composite in range(prime * prime, sieve_length, prime):                sieve[composite] = False    return sievedef compute_largest_prime_palindrome_below(limit):    sieve = produce_sieve(limit)    for prime in range(limit - 1, 1, -1):        if (sieve[prime] and is_palindromic(prime)):            return prime    raise ValueError('No primes found')if __name__ == __main__:    print(compute_largest_prime_palindrome_below(1000))
Snakes on a prime
python;beginner;programming challenge;primes;sieve of eratosthenes
IntroductionIt took me a good 30 hours to figure out this solution. However when one sees the drastic speed increases it produces it might have been worth it. Before I go into the performance optimizations I will give you some advice on the code you have writtenYour naming scheme is for the most part good. Good variable names should be descriptive, distinct and succinct in that order. You have nailed the first two, however I would try to also not make the names too long as it will hurt the readability of your code. The function name compute_largest_prime_palindrome_below could just as well be named largest_prime_palindrome without being less clear. Similarly is_palindromic could have been is_palindrome.You should include a https://www.python.org/dev/peps/pep-0257/ at the start of your code. You can never start too early with good documentation. Ask yourself are you sure you will understand your code a year down the road, what about 5 or 10?The while (integer != 0): is superfluous. Python treats 0 as false, so you could have written while integer:. I will not comment on the parenthesis, since you have already mentioned these.You still have inconsistent spacing in your code. This symbolizes to me a lack of detail. Improving your algorithmYou use a very simple prime sieve to find the primes. However there exists much faster primesieves out there. Here is a large list of sieves, pick your favorite. My favorite is the primesieve library. Here is a description of the Python  implementation. If you are on windows this can be installed from the command window using pip install primesieveYour code can now be written as. from primesieve import generate_primesdef is_palindromic(integer):    return integer == reverse(integer)def largest_prime_palindrome_2(limit):    for prime in reversed(generate_primes(limit)):        if prime and is_palindromic(prime):            return prime    raise ValueError('No primes found')This gives me a speed increase of about \$40\$ times. However we can do slightly better than this. One problem with your code is that you use Memoization and store all the primes up to $N$. For large values this takes up a lot of memory. If you try \$10^9\$ or \$10^{11}\$ you can be sure that your computer will quickly run out of memory. An alternative is to use a prime generator instead of creating all the values. from primesieve import Iteratordef is_palindrome(num):    num_str = str(num)    return num_str == num_str[::-1]def biggest_palindrome_prime_faster(limit):    it = Iterator()    it.skipto(limit)    prime = it.previous_prime()    while prime > 0:        if is_palindrome(prime):            return prime        prime = it.previous_prime()For \$10^5\$ this gives a \$400\$ times speed increase over your implementation for \$10^5\$. The code should be self explanatory, but feel free to ask if you have any questions. You can also check out the package documentation. New algorithmYour algorithm iterates over the primes and then check if it is palindrome.However we can switch this around and rather iterate over the palindromes and check for primality. There are many advantages with this method.We only have to iterate over palindromes with odd length. All palindromes with even length are divisible by \$11\$ and hence not prime. We can skip palindromes ending in a even digit or \$5\$, since these are not primesYou do not run out of memory, since we generate palindromes on the fly. By starting at the largest values we can stop once we find a prime.Checking primality is much faster than creating a list of all primes. As an example I can show that a \$4\$ digit palindrome, will be divisible by \$11\$.Any palindrome of length \$4\$ can be written as \$abba\$. This is the same as$$1000a + 100b + 10b + a = 1001a + 110b = 11 (91a + 10b)$$The more general proof is included above. So if we have a number with even digits we know there will be no solutions. Any odd digit palindrome can be written on the form$$[\text{digit}] \ + \ \text{second} \ + \ [\text{middle}] \ + \ \text{second_reverse} \ + \ [\text{digit}]$$No prime > 2 can end in [2, 4, 6, 0, 5]. So the first digit can only be [1, 3, 7, 9], since this is also the last digit. The middle can be any number in [0-9]and the \$\text{second}\$ can be any number with a certain length. Say our number has n digits.Then \$\text{second}\$ has to have a length of \$\text{floor}(n/2)-1\$.Take \$5\$ for instance, then we use \$1\$ digit in front, \$1\$ in the back and one in the middle. This leaves \$5-3 = 2\$ for the two second numbers, so each second has to have \$1\$ digit. Similarly \$\text{floor}(n/2) -1 = 2 - 1 = 1$.To generate numbers with n digits, we can use the Cartesian Product. This can be imported from the itertools module. As an exampleprint(list(product([1,2,3], repeat = 2)))[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]Using all of these ideas the final code to iterate over the palindromes can be written asdef largest_palindrome_prime(num):    digits = len(str(num))-1    if digits % 2 == 0:        digits -=1    middle_digit = map(str, range(9, -1, -1))    for first in ['9', '7', '3', '1']:        for perm in product(middle_digit, repeat = digits//2-1):            second = ''.join(perm)            for middle in middle_digit:                palindrome = int(first + second + middle + second[::-1] + first)                if isprime(palindrome):                    return palindromeThe first part makes sure that we are rounding down to the closes palindrome with odd length. The isprime function you have to write yourself. If you want you can see my answer on how to write a good prime checker.This now gives a rough \$ 1500 \$ speed increase over your naive implementation. Speed comparisonsI ran \$1000\$ runs for all the functions below. The first valueis the running time of your implementation. Then I timed how many times faster my implementation was. To be fair I only timed odd powers since there are no prime palindromes of even length as discussed earlier. limit        naive   new_sieve    Iterator   palindrome---------------------------------------------------------  10^3 |     1.0 ms         7.0      21.277       19.568  10^5 |    32.0 ms      62.105     457.425     1692.082  10^7 |  3740.0 ms      89.969    9194.808    34402.762---------------------------------------------------------For the lowest values palindrome seem to be performingworse than the Iterator, however it is still a clear improvement.I then further compared Iterator and Palindrome below. The reason why I did not test yours or the improved sieve is that they take too long to run.   limit     Iterator   palindrome      ratio----------------------------------------------  10^7  |   1.225 ms     0.265 ms      4.629   10^9  |  11.973 ms     0.242 ms     49.544  10^11 |  33.632 ms     0.287 ms    117.119   10^13 | 291.021 ms     0.282 ms   1032.654 ----------------------------------------------Seems like the power does not really matter to the palindrome. Just for fun I tested the palindrome function for some really high values.  limit          Palindrome-------------------------------------------  10^25  |  4.6782084283 ms  10^51  | 20.3384558935 ms  10^75  |  7.3286887458 ms  10^101 | 79.0633348572 ms-------------------------------------------The isprime function I used for Palindrome can be found in this answer.I used the Miller-Rabin and not the isprime from the prime_fac module.However that should only cause minor differences.