[백준] 1747 소수 & 팰린드롬 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1747
• 🔑 에라토스테네스의 체
  • 에라토스테네스의 체를 사용해 소수를 미리 구해둔다.
  • 최대 입력값인 1000000이 들어오면 1003001이 정답이므로 넉넉한 크기까지 구함
  • 구한 소수들을 n번부터 시작해서 순회하면서 팰린드롬인 소수를 찾는다.
  • 문자열[::-1]을 하면 문자열을 뒤집을 수 있음

 

n = int(input())

prime = [True] * (1_030_001)
prime[1] = False

for i in range(2, int(1_030_000 ** 0.5) + 1):
    if prime[i]:
        for j in range(i*2, 1_030_000 + 1, i):
            prime[j] = False

for i in range(n, len(prime)):
    if prime[i]:
        if str(i) == str(i)[::-1]:
            print(i)
            exit()