[Python/파이썬] 백준 1990번 소수인팰린드롬

1990번: 소수인팰린드롬

 

문제

151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되고 이 두 수가 다르기 때문에 팰린드롬이 아니다. 두 정수 a, b가 주어졌을 때, a이상 b이하인 소수인 팰린드롬을 모두 구하는 프로그램을 작성하시오.

입력

입력은 첫째 줄에 공백으로 구분된 두 자연수 a, b가 주어진다. 단 5 ≤ a < b ≤ 100,000,000 이다.

출력

첫째 줄부터 차례로 증가하는 순서대로 한 줄에 한개씩 소수인 팰린드롬을 출력한다. 마지막 줄에는 -1을 출력한다.

코드

from math import sqrt

a, b = map(int, input().split())

def palindrom(num):
    str_num = str(num)
    l = len(str_num)
    for i in range(l):
        if str_num[i] != str_num[l-1-i]:
            return False
    return True

for i in range(a, min(b+1, 10_000_000)):
    flag = True
    if palindrom(i):
        for j in range(2, int(sqrt(i))+1):
            if i % j == 0:
                flag = False
                break
        if flag:
            print(i)
            
print(-1)

처음에는 에라토스테네스의 체를 이용하여 소수를 판별하고 소수인 수들만 팰린드롬인지 확인하게 하였는데 메모리 초과가 발생하였다. 에라토스테네스의 체를 사용하려면 구하려는 수를 크기로 하는 배열이 필요하기 때문이었던거 같다.

 

그래서 질문 게시판에서 찾아본 결과, 자릿수가 짝수인 소수인팰린드롬은 11 말고는 없다는 힌트를 얻었고, 팰린드롬을 먼저 판별하고 팰린드롬인 수에 대해서만 소수 판별을 하면 되겠다는 생각이 들었다. 에라토스테네스의 체를 사용하지 않고, 나눠지는 수가 있는지만 확인하면 되기 때문에 시간 초과 문제도 해결할 수 있기 때문이었다.

 

그런데 이렇게 해도 시간 초과가 발생하길래 다시 찾아봤더니 10,000,000 이상인 수 중에는 소수인팰린드롬수가 존재하지 않는다고 한다. 자릿수가 짝수인 소수인팰린드롬은 존재하지 않는다고 했고, b의 범위는 100,000,000까지이니까 당연한건데 이걸 놓쳤던것 같다. b가 10,000,000보다 큰 경우에는 10,000,000까지만 계산해보도록 바꿨더니 시간 초과가 해결됐다.