2

So I'm trying to figure out how to find all the palindrome prime numbers between 2 numbers. So far my code can find the palindrome but when I check for a prime number, it prints out the non-primes as well. And there are numbers which are printed multiple times.

Could you please help.

Thanks.

a = 0
b = 500
a += 1   
for i in range(a,b):
    if(str(i) == str(i)[::-1]):
        if(i>2):
            for a in range(2,i):
                y = True
                if(i%a==0):
                    y = False
                    break
            if y:
                print(i)
Sab ಠ_ಠ
  • 135
  • 1
  • 4
  • 13
  • 2
    It might be helpful to modularize your code more, i.e. add a `is_prime()` function and `is_palindrome()` function. This will definitely make it more readable *the hallmark of python* – C.B. Mar 27 '14 at 21:32
  • 2
    You `print(i)` immediately after the palindrome check – wim Mar 27 '14 at 21:33
  • And never set `y` to `True` again, either. – a p Mar 27 '14 at 21:34
  • You use a print right after the test for palundromes happen, without considering primality – elias Mar 27 '14 at 21:34
  • Also, could you please explain what the last line is used for? – elias Mar 27 '14 at 21:36
  • @elias the last line shouldn't be here and the first print as well. I was just trying to find my mistakes by adding additional code. Edited to what the original code was and I get 3 as the only output. – Sab ಠ_ಠ Mar 27 '14 at 21:37
  • Ok, thanks for clarifying. I don't want to give away the solution, but I recommend to renaming your variables, so their names explain what they are used for. That sure will help you to identify what's happening with one of your variables, where nothing should happen with it. Thumbs up! – elias Mar 27 '14 at 21:41
  • Move `y = True` to the first line of your `for` loop. Based on the changes you've made in your most recent edit I believe that ought to do it. (You have to reset it for each number, so you do the entire check for each.) – 2rs2ts Mar 27 '14 at 21:46
  • @2rs2ts it's better now but loads of numbers are missing. See my updated code. – Sab ಠ_ಠ Mar 27 '14 at 21:51
  • No, I meant your first `for` loop. `for i in range(a,b):`. Although I suppose it doesn't matter. – 2rs2ts Mar 27 '14 at 21:54
  • @2rs2ts It doesn't work there, it prints the same number loads of times and it also prints the non-primes. – Sab ಠ_ಠ Mar 27 '14 at 21:55
  • You aren't writing what I'm trying to say. I answered so you can see the entire code. – 2rs2ts Mar 27 '14 at 22:04

4 Answers4

4

Based on your most recent code, you simply need to make sure that you reset y, which serves as your positive indicator of primality, for each number you test. Otherwise, it will stay False when you get to the number 4, the first composite number.

>>> a = 0
>>> b = 500
>>> a += 1
>>> for i in range(a,b):
        y = True
        if(str(i) == str(i)[::-1]):
            if(i>2):
                for a in range(2,i):
                    if(i%a==0):
                        y = False
                        break
                if y:
                    print(i)


3
5
7
11
101
131
151
181
191
313
353
373
383

As you can see, all of these are prime. You can check the list of primes wolframalpha provides to be sure that no palindromic primes have been omitted. If you want to include 2, add a special case for that.

2rs2ts
  • 10,662
  • 10
  • 51
  • 95
  • 1
    I got exactly the same thing. I though some were missing because I forgot for some time it was palindromic prime I was looking for. Thanks a lot. – Sab ಠ_ಠ Mar 27 '14 at 23:13
  • 1
    I still cannot see, why the condition `if(i>2)` is necessary. This is what prevents number 2 to be printed, so it should be changed to `if(i>1)`, or for even better efficiency, completely removed, and the line `a = max(a+1, 2)` used instead of the line `a += 1`. – elias Mar 28 '14 at 12:22
2

Please see my comments below:

a = 0
b = 500
a += 1
y = True
for i in range(a,b):
    if(str(i) == str(i)[::-1]):
        print (i)      # <--- You print every number that is a palindrome
        if(i>2):
            for a in range(2,i):
                if(i%a==0):
                    y = False   # <--- This never gets set back to True
                    break
            if y:
                print(i)

        i+=i   # <--- This is doing nothing useful, because it's a "for" loop
wim
  • 338,267
  • 99
  • 616
  • 750
0

Look at my code below, we don't need to initialize Y as well. A For-Else block works well.

a = 0
b = 500
a += 1
for i in range(a,b):
    if(str(i) == str(i)[::-1]):
        if(i>1):
            for a in range(2,i):
                if(i%a==0):
                    y = False
                    break
            else:
                print(i)

To get 2 included in the answer, just be sure to check the if condition as (i>1) as mentioned by @elias

Sagar
  • 35
  • 5
0

Here is the pretty fast implementation based on "Sieve of Atkin" algorithm. I calculate all primes numbers up to the end and then filter only palindromic ones where number is greater or equal to start.

import math
import sys

def pal_primes(start,end):
    return list(filter(lambda x: str(x)==str(x)[::-1] and x>=start, sieveOfAtkin(end)))
    
    def sieveOfAtkin(limit):
        P = [1,2,3]
        sql = int(math.sqrt(limit))
        r = range(1,sql+1)
        sieve=[False]*(limit+1)
        for x in r:
            for y in r:
                xx=x*x
                yy=y*y
                xx3 = 3*xx
                n = 4*xx + yy
                if n<=limit and (n%12==1 or n%12==5) : sieve[n] = not sieve[n]
                n = xx3 + yy
                if n<=limit and n%12==7 : sieve[n] = not sieve[n]
                n = xx3 - yy
                if x>y and n<=limit and n%12==11 : sieve[n] = not sieve[n]
        for x in range(5,sql):
            if sieve[x]:
                xx=x*x
                for y in range(xx,limit+1,xx):
                    sieve[y] = False
        for p in range(5,limit):
            if sieve[p] : P.append(p)       
        return P
    
    
    if __name__=="__main__":
        print(pal_primes(int(sys.argv[1]),int(sys.argv[2])))

Based on this thread:

Sieve Of Atkin Implementation in Python

bergee
  • 111
  • 5