CODEWITHSUNDEEP
pythonlistprimes
Kr Milind
Kr Milind

Reputation: 11

To find a prime palindrome number

I have to print nth prime palindrome number with the help of this program, where n is number given by the user but I have a problem in this program, as it is taking much time to print the answer.

n=int(input())
l=[]
for i in range(1,1000000):
    y=True
    if str(i)==str(i)[::-1]:
        if i>=2:
            for j in range(2,i):
                if i%j==0:
                    y=False
                    break     
            if y:
                l.append(i)
print("Your Prime Palindrome Number Is:",l[n-1])

How can I make this code time efficient?

Upvotes: 0

Views: 567

Answers (1)

Adon Bilivit
Adon Bilivit

Reputation: 27105

The first part of this code is not specific to this question. It's a general purpose strategy for testing prime numbers. It's faster than sympy.isprime() for values lower than ~500,000 (Python 3.11.1 on Intel Xeon) after which the sympy version betters this implementation.

from math import sqrt, floor

def isprime(n):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, floor(sqrt(n))+1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

Now you need something to test for a palindrome. This function will return True if the string representation of the object is palindromic.

def ispalindrome(o):
    return (_ := str(o)) == _[::-1]

And this is the main part of the program. As 2 is the only even prime number, let's treat that as a special case. Otherwise start with 3 and just test subsequent odd numbers.

N = int(input('Enter value for N: '))

if N > 0:
    if N == 1:
        print(2)
    else:
        p = 3
        while True:
            if isprime(p) and ispalindrome(p):
                if (N := N - 1) == 1:
                    print(p)
                    break
            p += 2

Sample output:

Enter value for N: 11
313

Upvotes: 1

Related Questions