백준 1747번 소수&팰린드롬 파이썬

문제

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

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

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

예제 입력 1

31

예제 출력 1

101

제출 답안

import math
import sys
 
input = sys.stdin.readline
 
m = 1004000
n = int(input())
array = [True for i in range(m + 1)]
min_num = 0
 
for i in range(2, int(math.sqrt(m)) + 1):
    if array[i] == True:
        j = 2
        while i * j <= m:
            array[i * j] = False
            j += 1
 
for i in range(n, m + 1):
    if array[i] and str(i) == str(i)[::-1] and i != 1:
        print(i)
        break
    elif i == 1:
        print(2)
        break

1. n의 범위가 1,000,000까지라 우선 m을 int(1e7)정도로 두고 돌려서 최대값을 뽑아서 m을 다시 지정하였다.
2. 모두 true로 두고 false로 업데이트해서 true인것만 찾는다.
   1. 2부터 시작해서 배수를 false로 만들면 소수만 남는다.
3. 소수이면서 팰린드롬인거를 찾기 위해서 array에 대입해보고 문자열로 만들어서 리버스 한거랑 값으면 출력한다.
4. 여기서 1은 2가 나와야 해서 따로 조건을 주었다.