How to generate prime palindromes in Python 3

Question

I'm trying to generate the prime palindromes between two integers (given by the user) and simply can't figure out where I'm going wrong. Please can someone explain?

Here's what I've got so far:

#Palindrome test
def palindrome(num):
    str(num) == str(num)[::-1]

#Prime test (excl. 3, 5 & 7 because not palindrome)
def prime(num):
    abs(num)%2 != 0
    abs(num)%3 != 0
    abs(num)%5 != 0
    abs(num)%7 != 0


N = int(input("Enter the start point N: "))
M = int(input("Enter the end point M: "))

for x in range(N, M):
    if palindrome(x) and prime(x):
        print(x)

Alright, as was pointed out - there's more than one issue in the code above. I've tried again and come up with this (below), which manages to print out all the palindromes, but also includes the non-prime numbers. Where am I going wrong?

N = int(input("Enter the start point N: "))
M = int(input("Enter the end point M: "))

def palindrome(num):
    return str(num) == str(num)[::-1]

def prime(x):
    for x in range(N, M+1):
        for y in range(2, x):
            if x%y != 0:
                return True

for z in range(N, M):
    if palindrome(z) and prime(z):
        print(z)

Thanks for all the feedback so far!

Answer 1

See if this works

#Palindrome test
def palindrome(num):
    return str(num) == str(num)[::-1]

#Prime test (excl. 3, 5 & 7 because not palindrome)
def prime(num):
    if abs(num)%2 != 0 and abs(num)%3 != 0 and abs(num)%5 != 0 and  abs(num)%7 != 0:
        return True
    return False

BTW - 143 is not a prime number but your prime test will return true. Not sure if that is by design.

Edit: Yes I am aware of the fact that the prime test is incorrect. I have simply taken OP's code the way he is using it.

Try using this for checking primes

def prime(int x):
    if x < 0: x *= -1
    i = 2
    while i*i <= x:
        if x % i == 0: return False
        i += 1
    return True

Answer 2

I took @Banach code little further. Test for prime is changed to accommodate numbers that are divisible by prime numbers itself. Inspiration from here.

The prime test now works for much larger numbers as well.

Demo Code

#Palindrome test
def palindrome(num):
    return str(num) == str(num)[::-1]

#Prime Test
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

#Get user input
N = int(input("Enter the start point N: "))
M = int(input("Enter the end point M: "))

for x in range(N, M):

    #Check for palindrome and prime number
    if palindrome(x) and is_prime(x):

        #Omitting 2,3,5,7 as per request
        if abs(x)%2 != 0 and abs(x)%3 != 0 and abs(x)%5 != 0 and  abs(x)%7 != 0:
            print(x)

Output

Python 2.7.9 (default, Dec 10 2014, 12:24:55) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
Enter the start point N: 2
Enter the end point M: 20000
11
101
131
151
181
191
313
353
373
383
727
757
787
797
919
929
10301
10501
10601
11311
11411
12421
12721
12821
13331
13831
13931
14341
14741
15451
15551
16061
16361
16561
16661
17471
17971
18181
18481
19391
19891
19991
>>> 

Answer 3

This seems like a fun problem. If you have an industrial-strength test like the Miller Selfridge Rabin test for primality, you can find some real large examples (albeit with a vanishingly small probability of getting a composite):

import random

#The following function finds s and d in
#n-1 = 2^s*d with d odd

def findSD(n):
    s = 0
    d = n-1
    while d % 2 == 0:
        s = s + 1
        d = d//2
    return s,d

def checkBase(a,n):
    s,d = findSD(n)
    x = pow(a,d,n)
    if x == 1 or x == n-1:
        return "probable prime"
    else:
        for i in range(s-1):
            x = pow(x,2,n)
            if x == 1:
                return "composite"
            elif x == n-1:
                return "probable prime"
        #if you get to this stage, -1 not reached despite s-1
        #squarings -- so must be composite
        return "composite"

def MSR(n,k):
    #tests if an odd number is prime
    for i in range(k):
        a = random.randint(2,n-2)
        if checkBase(a,n) == "composite":
            return "composite"
    #if you get here n has survived k potential witnesses, so
    return "probable prime"

def prime(n):
    smallPrimes = [2,3,5,7,11,13,17,19]

    for p in smallPrimes:
        if n == p:
            return True
        elif n % p == 0:
            return False

    if MSR(n,20) == "composite":
        return False
    else:
        return True

def randOddPalindrome(n):
    digits = [random.choice('13579')]
    if n > 1:
        m = (n-2)//2
        digits.extend(random.choice('0123456789') for i in range(m))
        digit = [''] if n%2 == 0 else [random.choice('0123456789')]
        digits += (digit + digits[::-1])
    return int(''.join(digits))

def findPrimePalindrome(n,trials = 10000):
    for i in range(trials):
        p = randOddPalindrome(n)
        if prime(p): return p
    return "No primes found in " + str(trials) + " trials"

for example,

>>> findPrimePalindrome(5)
30803
>>> findPrimePalindrome(6)
'No primes found in 10000 trials'
>>> findPrimePalindrome(101)
10411470210071416936952003803463770311632555360794349706355523611307736430830025963961417001207411401

I briefly suspected a bug when I saw the output for n=6 but then realized that 11 is the only prime palindrome with an even number of digits since all palindromes with an even number of digits are multiples of 11.