CodeEval Prime Palindrome

Find the largest prime palindrome less than 1000. Such a simple request is CodeEval problem #3.

It doesn't make sense writing a test case in this case, we can just ensure that our code, in this case my python script, generates the expected solution, 929.

I have split the job in two parts. We are looking for a palindrome number of three ciphers. So, we want its first and last cipher to be the same:
for candidate in range(989, 100, -2):  # 1
    if (candidate // 100 == candidate % 10) and is_prime(candidate):  # 2
        print(candidate)
        break
1. I should have started looping from 999. However, this number is evidently not prime. So I started from the second palindrome available. I step by 2, downward, since I don't care about even numbers, being them not prime.
2. If I divide the candidate number by one hundred, I get the third, most significative, cipher. This is Python 3, so I use the // to apply the integer division. The remainder of the division by ten gives us the less significative cipher. They should be the same.

But this is not enough, the candidate should also be a prime number. We all know how to check if a number is prime. We ensure that it has no divisor besides one and itself. A safe trick is stopping checking when we reach the square root of the tested number. This lead to this function:
PRIMES = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31]  # 1


def is_prime(value):
    for prime in PRIMES:  # 2
        if prime**2 > value:  # 3
            break;
        if value % prime == 0:  # 4
            return False

    return True
1. Sort of cheating. Since I know that the biggest number I have to check is less than 1024, I need only prime numbers less than 32. It is easy to find out the list of them.
2. I am going to check the value against the prime numbers in the list.
3. It is cheaper to get the square of a number that a square root, so I inverted the check to determine if I can safely stop to loop on primes. Notice that I can't merge this check in the one in (2) even if it has to be performed on each cycle. That's Python, love it or leave it.
4. Only if no divisor is found, return true.

I guess you won't need to see the full python script. However I pushed it to GitHub.

No comments:

Post a Comment