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

1747번: 소수&팰린드롬

분류

• 수학
• 브루트포스 알고리즘
• 정수론
• 소수 판정
• 에라토스테네스의 체

문제

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

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

입력

첫째 줄에 N이 주어진다.

출력

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

풀이

• 소수이면서 펠린드롬인 수를 구해야 한다.
• N이상 인 수 중에 가장 작은 수를 구해야 하는데 N의 범위는 1 ≤ N ≤ 1,000,000이다.
• 즉, 최대 N이 100만이 될 수 있다.
• 따라서 소수를 구하는 대상이 1000000이 아니라 그 이상이어야 한다.
• 그래서 범위를 1005000으로 지정했다.
• 범위를 너무 늘리면 시간초과나 메모리초과가 발생하기 때문에 범위를 잘 설정하는 것이 중요한 것 같다.

코드

N = int(input())
m = 1005000
arr = [True]*(m)
arr[0],arr[1]=False,False
# 소수 구하기
for i in range(2, m):
    if not arr[i]:continue
    j=2
    while i*j<m:
        arr[i*j]=False
        j+=1
# 소수일 경우 펠린드롬인지 확인하고 맞다면 break
while 1:
    if arr[N]:
        tm = str(N)
        if tm ==tm[::-1]:
            print(int(tm))
            break
    N+=1