68일차 문제

문제풀이

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

예제 입력 1
31

예제 출력 1
101

a = int(input())
pl = [0]*1003002
pl[1] = 1
for i in range(2, a):
  if pl[i]==0:
    for j in range(i, 1003002, i):
      pl[j] = 1
for i in range(a, 1003002):
  if pl[i]==0:
    if str(i) ==str(i)[::-1]:
      print(i)
      break
    else:
      for j in range(i, 100302,i):
        pl[j]=1

에라토스테네스의 체를 이용해서 윗 반복문에서 소수를 찾은 후 아래 반복문을 통해서 펠린드롬에 적합한 수를 찾는다.