[🥈1 / 백준 1747 / 파이썬] 소수&팰린드롬

 

1747번: 소수&팰린드롬

 

문제

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

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

입력

첫째 줄에 N이 주어진다.

출력

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

 

예제 입력 31

예제 출력 101

 

풀이

 

소수 판별과 팰린드롬을 동시에 구하는 문제이다.

우선 에라토스테네스의 체로 충분한 크기의 소수 리스트를 구한다.

입력의 최대값인 1,000,000의 정답에 해당하는 소수는 1,003,001이다.

따라서 2부터 1,003,001까지의 소수 리스트를 구하면 되겠다.

 

그 다음, n이상인 소수 리스트를 훑으며 팰린드롬을 찾아 출력하면 된다.

 

n = int(input())
prime = [False]*2 + [True]*1003000

for i in range(2,int(len(prime)**0.5)+1):
    prime[i*2::i] = [False]*len(prime[i*2::i])

for i in range(n,len(prime)):
    if prime[i] and str(i) == str(i)[::-1]:
        print(i)
        break