Max Prime Palindrome in Python

Question

I'm trying to create a program that outputs the highest prime number than is a palindrome and is less than 1000. Expected output should be 929

Attempt 1

number = 1
prime = 1
maxNumber = 1000

while number > maxNumber:
    if str(number) == str(number)[::-1]:        #Inverts the string
        for number in range(number,maxNumber):  #Increments number until 1000
            for i in range(2, number):          #Checks current number and divides all lower
                if number % i == 0:
                    break
                else:
                    prime = number              
print(prime)

Attempt 2

number = 3
prime = 3
maxNumber = 1000

while number < maxNumber:
    if str(number) == str(number)[::-1]:        #Inverts the string
        for i in range(2, number):
            if number % i == 0:
                break
            else:
                prime = number
        number+=1
print(prime)

Attempt 3, I followed the suggestions to separate the two functions to decrease processing time

for number in xrange(1000):
    if str(number) == str(number)[::-1]: and is_prime(number):
        prime = number
print(number)

#Method to find prime numbers
def is_prime(n):
    if n == 2 or n == 3: 
        return True
    elif n < 2 or n%2 == 0: 
        return False
    elif n < 9: 
        return True
    elif n%3 == 0: 
        return False
    r = int(n**0.5)
    f = 5
    while f <= r:
        if n%f == 0: 
            return False
        if n%(f+2) == 0: 
            return False
        f +=6
    return True

Attempt 4: Receiving the error [name 'is_prime' is not defined]

for number in range(1000,3,-1):
    if str(number) == str(number)[::-1] and is_prime(number):      
        print(number)  
        break  

#Method to check if number is prime  
def is_prime(n):
    if n == 2 or n == 3: return True
    if n < 2 or n%2 == 0: return False
    if n < 9: return True
    if n%3 == 0: return False
    r = int(n**0.5)
    f = 5
    while f <= r:
        if n%f == 0: return False
        if n%(f+2) == 0: return False
        f +=6
    return True

Final Solution: Thank you all for your help. This has been more helpful than I have ever expected.

#Method to check if number is prime  
def is_prime(n):
    if n == 2 or n == 3: return True
    if n < 2 or n%2 == 0: return False
    if n < 9: return True
    if n%3 == 0: return False
    r = int(n**0.5)
    f = 5
    while f <= r:
        if n%f == 0: return False
        if n%(f+2) == 0: return False
        f +=6
    return True  

#Checking for numbers that are palindromes and prime
for number in range(1000,3,-1):
    if str(number) == str(number)[::-1] and is_prime(number):
        print(number)  
        break

Your condition is backwards. Change `while number > maxNumber:` to `while number < maxNumber:` You also have some logic errors elsewhere, but this will get you started debugging. — Jake Griffin, Apr 21 '15 at 14:23
@JakeGriffin Why comment and answer the exact same thing? Double the effect? — miradulo, Apr 21 '15 at 14:24
I deleted the answer because of the other logic errors and posted it as a comment instead. — Jake Griffin, Apr 21 '15 at 14:25
Thanks, I can't believe I reversed the condition, going to look for the logic errors in the code — Andy Wong, Apr 21 '15 at 14:27
A hint for the other logic errors: The `while` loop will already repeat the contents of it. Instead of including a `for` loop for iterating from 1 to 1000, try just incrementing `number` at the end (`number += 1`). — Jake Griffin, Apr 21 '15 at 14:36
No problem. If you get stuck again, just update what code you have and let us know how we can help. — Jake Griffin, Apr 21 '15 at 14:45
I made some changes but I'm still not getting and output, I'm suspecting is my for loop logic — Andy Wong, Apr 21 '15 at 14:59
Do you want all the palindromes less than 1000 or the max prime number less than 1000? Why do you keep pulling the print out of the loop? There are more than 1 numbers less than 1000 that are palindromes... — dawg, Apr 21 '15 at 15:32
@dawg Sorry for not being clear, I just want the highest palindrome prime which is less than 1000, so I'm expecting an output of 929 — Andy Wong, Apr 21 '15 at 15:34
Attempt 4: You need to define `is_prime` BEFORE you call it. i.e., put it above the `for` loop in the source file so the interpreter knows what `is_prime` is. — dawg, Apr 21 '15 at 15:59
@dawg Ah, I can't tell if it was Java that made me assume the order did not matter. It is compiling now with 929. Thank you all so much. — Andy Wong, Apr 21 '15 at 16:09

score 2 · Accepted Answer · edited May 23 '17 at 10:28

There are several issues with your code:

First version, your logic for the while loop is backward
Second version, your indentation is wrong. number+=1 is part of the if block above and the print is not part of the while loop.
The print at the end of the while loop is print the wrong value since it has dropped out of the loop at this point for the test while number < maxNumber:.

Try:

for n in xrange(1000):
    if str(n)==str(n)[::-1] and is_prime(n):
        print n

Which you can turn into a while loop easily:

n=0
while n<1000:
    if str(n)==str(n)[::-1] and is_prime(n):
        print n
    n+=1

I suggest separating out the prime testing from the palindrome testing. Since testing a string for being a palindrome is fast in comparison to testing if a number is a prime (for larger numbers) test for a palindrome first.

There is a function for testing a number as being a prime here.

Based on your comments, I now see you are looking for the max and not all of the prime palindromes.

To get the max prime palindrome, you can just step backwards from the max value. Since you do not know if that max value is prime or not or even or not, you need to step by -1 (or write some additional code that confuses the concept):

for number in range(1000,3,-1):
    if str(number) == str(number)[::-1] and is_prime(number):      
        print(number)  
        break

Which you can make 'Pythonic' by just using next and a generator:

>>> next(n for n in range(1000,3,-1) if str(n)==str(n)[::-1] and is_prime(n)) 
929

Or, use max with a list of the primes (way less efficient since you have to generate them all):

>>> max(n for n in range(1000) if str(n)==str(n)[::-1] and is_prime(n)) 
929

Also, instead of testing for palindromes, one could simply generate palindromes. Iterating over 3 digits palindromes is nothing but iterating over (a, b) in [0..9] x [0..9] and considering (a, b, c) — SylvainD, Apr 21 '15 at 15:45
@Josay: True, but the audience seems to be a Python beginner. Let's walk before we run, no? Cheers! — dawg, Apr 21 '15 at 15:49
You all provide excellent advice on shortcuts, Yes I'm a beginner but I can already see how there are more interesting ways to solve this question — Andy Wong, Apr 21 '15 at 15:52

Max Prime Palindrome in Python

1 Answers1