[Python][백준 1747] 소수&팰린드롬

Date: 2025.01.30 Updated: 2025.02.01

태그: coding test 백준 1747 소수 에라토스테네스의 체 팰린드롬 python

🔄 소수&팰린드롬 문제 풀이

백준 1747번 소수&팰린드롬 문제의 파이썬 풀이

📝 문제 설명

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79197과 324423 등이 팰린드롬 수이다. 입력으로 주어진 수보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서 가장 작은 수를 구하는 프로그램을 작성하시오.

💡 풀이

이 문제는 두 가지 조건을 모두 만족하는 수를 찾아야 한다.

소수여야 함
팰린드롬이어야 함

에라토스테네스의 체로 일부 소수를 미리 구해놓고, 입력값부터 시작하여 각 수가 팰린드롬인지 확인한 뒤 소수를 찾는다.

🔍 코드 설명

팰린드롬 판별 함수 구현:
- 문자열로 변환하여 뒤집은 것과 비교
에라토스테네스의 체로 소수 생성:
- 특정 범위까지의 소수를 미리 계산
주어진 수부터 시작하여:
- 팰린드롬인지 확인
- 소수인지 확인
- 두 조건을 모두 만족하면 그 수를 반환

✨ 참고

에라토스테네스의 체로 일부 소수를 미리 구해두면 효율적이다.

🎯 주의사항

입력값이 1인 경우를 고려해야 한다.
결과값이 항상 존재한다.

📝 코드

import sys

def is_palindrome(num):
    """주어진 숫자가 팰린드롬인지 확인하는 함수"""
    return str(num) == str(num)[::-1]

def generate_primes(limit):
    """에라토스테네스의 체를 사용하여 limit 이하의 모든 소수를 구하는 함수"""
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False  # 0과 1은 소수가 아님

    for num in range(2, limit + 1):
        if is_prime[num]:  # 소수이면 그 배수를 제거
            for multiple in range(num * num, limit + 1, num):
                is_prime[multiple] = False

    return [num for num, prime in enumerate(is_prime) if prime]

def find_smallest_prime_palindrome(n):
    """n 이상인 가장 작은 소수이면서 팰린드롬인 숫자를 찾는 함수"""
    prime_list = generate_primes(1004)  # 1004 이하의 소수 미리 계산

    # n부터 시작하여 가장 작은 소수 & 팰린드롬 찾기
    num = n
    while True:
        if num == 1:  # 1은 소수가 아님
            num += 1
            continue
        if is_palindrome(num):
            # 미리 계산한 소수 리스트에서 찾거나, 직접 판별
            if num in prime_list or all(num % p != 0 for p in prime_list if p * p <= num):
                return num
        num += 1

# 입력 받기
n = int(sys.stdin.readline().strip())

# 결과 출력
sys.stdout.write(str(find_smallest_prime_palindrome(n)) + "\n")

감자