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

백준 1747 - 소수&팰린드롬

시간 제한 2초, 메모리 제한 256MB

# 문제

• 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다.
  • 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.
• 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 N이 주어진다.

출력

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

# 접근 방법

• 우선 소수를 구해주었다.
• 이 때 주의할 점은 100001까지가 아닌, 1000000보다 크거나 같은 소수 중 팰린드롬인 수까지 구해야 하므로 여유있게 1500000까지 구해주었다.
• 이후, bisect를 이용하여 N이 들어갈 index를 구해서 해당 index 부터 팰린드롬인 수를 찾을 때까지 for문을 돌려주었다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from bisect import bisect_left


N = int(input())
nums = []
check = [True] * 1003002
for i in range(2, 1003002):
    if check[i] == True:
        cnt = 2
        while i * cnt < 1003002:
            check[i*cnt] = False
            cnt += 1

for i in range(2, 1003002):
    if check[i] == True:
        nums.append(i)
idx = bisect_left(nums, N)
for i in range(idx, len(nums)):
    val = str(nums[i])
    left, right = 0, len(val) - 1
    flag = True
    while left <= right:
        if val[left] != val[right]:
            flag = False
            break
        left += 1
        right -= 1
    if flag:
        print(nums[i])
        break