CODEWITHSUNDEEP
pythonpython-3.xalgorithm
Anh Vu Nguyen
Anh Vu Nguyen

Reputation: 27

Finding nth Palindromic Prime - Where did I go wrong?

Given integer n (1<=n <=300), the code needs to return the nth Palindromic Prime.

I have written the below block of code to achieve the above, but for the life of me I cannot understand why my code isn't outputting the given expected value. Indeed I don't even know if it is my code that is wrong, or the given expected value is just bull. Would really appreciate some guidance.

Expected output: symmetricPrime2(72) returns 70507

Actual output: symmetricPrime2(72) returns 30103

def symmetricPrime2(n,candidate=2):
    primes = [2]
    counter = 1
    while True:
        i = 0
        prep = 0
        candidate = candidate + 1
        candidate_sr = str(candidate)
        #test if candidate is prime
        for prime in primes:
            if candidate%prime == 0:
                prep += 1
        #test if candidate is palindromic
        candidate_sr_rev = candidate_sr[len(candidate_sr)::-1]
        
        if prep == 0 and candidate_sr == candidate_sr_rev:
            primes.append(candidate)
        if len(primes) == n:
            break
    return primes[-1]

Upvotes: 0

Views: 469

Answers (3)

Tristan Nemoz
Tristan Nemoz

Reputation: 2048

There are several things that either are wrong or can be improved in your code.

  1. You can initialize primes with [2, 3] rather than [2], which allows you to start from candidate=3 and to increment it by 2 instead of 1, since 2 is the only even prime number.
  2. i = 0 has no point in your code
  3. prep is only used to test if candidate is prime. As soon as you find that candidate % prime is True, you can break out of your for loop, there is no need to continue to test it if you've already found out a divisor.
  4. The biggest mistake in your code: all primes are not palindromic. Of course you know this, but this is what you've written. Starting from 11, you only add primes to your list that are palindromic (you can test and see that 13 is not in primes for instance). Remove the and candidate_sr == candidate_sr_rev in your if so that you add primes to your list correctly. Since you want the n-th prime, you have two choices:
  • either you define a second list palindromic_primes to which you add every palindromic prime you've encountered and test its length to be equal to n
  • or you just keep the number of palindromic primes you've encountered and when this number is equal to n, you can return this palindromic prime number.

Upvotes: 1

avysk
avysk

Reputation: 2035

Your primality test is wrong as you add to primes only palindromic primes.

def symmetricPrime2(n,candidate=1):
    primes = []
    counter = 0
    while True:
        i = 0
        prep = 0
        candidate = candidate + 1
        candidate_sr = str(candidate)
        #test if candidate is prime
        for prime in primes:
            if candidate%prime == 0:
                prep += 1
        #test if candidate is palindromic
        candidate_sr_rev = candidate_sr[len(candidate_sr)::-1]

        if prep == 0:
            primes.append(candidate)
            if candidate_sr == candidate_sr_rev:
                counter += 1
        if counter == n:
            return candidate

Upvotes: 0

r3mainer
r3mainer

Reputation: 24587

You're testing numbers for primality based on whether or not they are divisible by numbers in the primes list, but you only add numbers to primes if they are palindromic. As a result, once you start encountering composite numbers with prime factors greater than 11, you're going to start identifying primes incorrectly.

According to your function, symmetricPrime2(12) == 323, but 323 is composite (17 × 19).

Upvotes: 1

Related Questions