[Python] 1990 소수인팰린드롬

[Gold V] 소수인팰린드롬 - 1990 

[문제 링크](https://www.acmicpc.net/problem/1990) 

---

💻 문제 정의

팰린드롬수란 151, 11 처럼 숫자를 앞에서 부터 읽은 것과 뒤에서 부터 읽은 것이 같은 수이다. 정수의 범위가 주어졌을 때, 소수이면서 동시에 팰린드롬인 수를 출력하는 문제이다.

💡 접근 및 설계

소수 판별 그리고 팰린드롬 판별 두 개의 로직이 필요하다. 소수 판별 알고리즘으로는 정석적인 풀이와 에라토스테네스의 체 기법을 활용하는 풀이, 두 가지 방법이 있다.

팰린드롬 판별은 문자열 뒤집기를 활용하였다.

✏️ 알고리즘 풀이

# 아마도 정석 소수 판별
def isPrime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    elif n >= 3:
        for i in range(2, n):
            if n % i == 0:
                return False
    return True

# 에라토스테네스의 체 - 최적화
def isPrime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

처음에는 정석 소수 판별 기법으로 문제를 접근하였으나, 역시나 시간초과가 발생하였다. 이후 소수 판별 함수를 에라토스테네스 체 기법으로 작성하였다.

isPalindrome = []
for i in range(a, b+1):
    if str(i) == str(i)[::-1]:
        isPalindrome.append(i)

팰린드롬 판별 방식은 다음과 같다. 문자열 뒤집기를 활용하여 팰린드롬을 판별하였다.

for p in isPalindrome:
    if isPrime(p):
        print(p)

이제 팰린드롬이면서 소수인 수를 출력하면 되나, 무슨일인지 자꾸만 시간 초과가 걸렸다. 해당 문제에 대해 원인을 알아보니..

if b > 10_000_000:
    b = 10_000_000

바로 다음과 같은 조건이 필요하였다.

팰린드롬 수 중에서 짝수 자리, 즉 1221, 145541 등과 같이 자릿수가 짝수이면 소수를 만족하지 않는다.(11의 배수). 따라서 천만 ~ 억 사이의 숫자들은 자릿수가 8자리이기 때문에 천만 이상의 수들은 판별 대상에서 제외하여도 무방하다.

🗒️ 최종 제출 코드

# 1990 소수인 팰린드롬

import math

def isPrime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

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

if b > 10_000_000:
    b = 10_000_000

isPalindrome = []
for i in range(a, b+1):
    if str(i) == str(i)[::-1]:
        isPalindrome.append(i)
# isPalindrome = [n for n in range(a,b+1)if str(n)==str(n)[::-1]]

for p in isPalindrome:
    if isPrime(p):
        print(p)
print(-1)

---

💭 오늘의 회고

골드 5 문제임에도 불구하고 정말 많은 생각을 요구하는 문제였다. 소수 판별 함수부터 팰린드롬 판별, 그리고 그 두개를 결합하였을때 발생하는 예외까지. 3박자를 갖춰야 하는 문제였다.