[문제 출처 : Codechef] 숫자 n이 주어졌을 때, n보다 큰 가장 가까운 자연수 중 소수이면서 회문인 m을 어떻게 찾을 수 있을까요? 여기서 우리가 기초훈련을 했던 것이 빛을 발할 시간입니다. [참고: 소수, 회문]

먼저, 주어진 수가 소수인지를 판단하는 함수를 선언하겠습니다. (자세한 설명은 소수를 참고하세요~)

def isPrime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    else:
        if n % 2 == 0:
            return False
        for i in range(3, int(n**0.5)+1, 2):
            if n % i == 0:
                return False
    return True

이미 우리는 굉장히 좋은 소수 찾기 알고리즘을 가지고 있기 때문에, 문제를 70% 이상은 해결했다고 볼 수 있습니다 :) 이제 주어진 n보다 크면서 회문(palindrome)이고 소수인 수를 찾아야 합니다. 그럼 여기서 잠깐 생각해봐야 하는게, 어떤 수가 회문일 확률이 높을까요, 소수일 확률이 높을까요? 놀랍게도 어느 것을 먼저 찾는 조건으로 사용하느냐에 따라 성능의 차이가 발생하게 됩니다! 아무래도 소수인지를 먼저 찾게 되면 $\sqrt{n}$번씩 연산을 해야 하는데, palindrome인지를 찾는 것은 $\frac{l}{2}$로써, 해당 숫자의 길이의 반만 연산하면 되기 때문에, palindrome인지를 먼저 체크하는 것이 시간을 단축하는 방법입니다 :)

def nearestPrimePalindrome_slow(n):
    if n % 2 == 0:
        n += 1
    while True:
        if isPrime(n): #slow 버전에서는 소수인지를 먼저 검사하고,
            if str(n)==str(n)[::-1]:
                return n
        n += 2

def nearestPrimePalindrome_fast(n):
    if n % 2 == 0:
        n += 1
    while True:
        if str(n)==str(n)[::-1]: #fast 버전에서는 회문인지를 먼저 검사합니다.
            if isPrime(n):
                return n
        n += 2

그럼 이제 성능 차이를 볼까요?

>>> from time import time
>>> import random
>>> n = random.randint(10000, 100000)
>>> print n
54472
>>> t0 = time()
>>> print nearestPrimePalindrome_slow(n)
70207
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 4.90e-02

>>> t0 = time()
>>> print nearestPrimePalindrome_fast(n)
70207
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 9.03e-03

얼추 4배정도 fast 버전이 빠르다는 것을 확인할 수 있죠!? 수가 커지거나 경우에 따라서는 더 벌어지기도 합니다. 그리고 최소한 fast 버전이 slow버전 이상의 성능을 낼 수 있다는 것은 다들 짐작하고 있으시겠죠? (둘 다 한번에 찾는 경우, 예를 들면 100을 입력했을 때, 101을 찾을 때는 둘 다 한번씩만 검사하기 때문에 시간이 동일합니다.)

정말 간단한 문제마저도 조금의 생각 차이가 큰 차이를 불러오네요!!