[BOJ][⚪1][백준#01747] 소수&팰린드롬

문제 출처

BAEKJOON Online Judge #1747

문제

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

입력

첫째 줄에 N이 주어진다.

출력

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

예제

입력

31

출력

101

My Sol

def isPal(x):
    x2 = ''.join(reversed(list(str(x))))
    return str(x)==x2

N = 1004000
v = [1]*N
v[0] = v[1] = 0
for i in range(2, N):
    if v[i]:
        for j in range(i+i, N, i):
            v[j] = 0

k = int(input())
while True:
    if v[k] and isPal(k): break
    k += 1

print(k)

소수의 개념을 생각하면 쉽게 풀 수 있는 문제였다. 2부터 시작해서 소수 체크가 안 되어 있는 수라면 해당 수의 배수들을 범위 내에서 모두 소수가 아님이라고 체크하는 방식이다. 입력된 수가 최대 100만이므로, 100만일 때의 100만보다 큰 소수이면서 팰린드롬인 수는 1003001 이므로 소수 체크 v의 크기 N은 넉넉히 1004000으로 잡아주었다.

복병은 1일 때인데, 1은 소수가 아니므로 1보다 크면서 팰린드롬인 소수는 2이다. 이 때문에 v를 정의하고 v[1]=0 처리해주어야 1이 입력되면 2가 출력된다.

결과

맞았습니다!!