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

https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

 

1. 난이도 실버1

 

주의할 부분

 

1. n으로 1이 주어진 경우 2가 출력되어야 한다. => 예외 처리 필요

 

2. 주어진 n의 범위가 1000000이지 소수&팰린드롬의 조건을 만족하는 수의 범위가 아니다!

따라서 for문의 범위를 더 크게 잡아줘야 한다.

나는 이 부분을 놓쳐서 엄청나게 틀렸고, 구글링을 한 결과 1000000보다 큰 수 중 조건을 만족하는 가장 작은 수가 1003001 이라고 해서 1004000으로 설정했다.

 

import sys
input = sys.stdin.readline

n = int(input().rstrip())

num = [True] * (1004000)

m = int(1004000 ** 0.5) #에라토스테네스
for i in range(2,m+1):
    if num[i] == True:
        for j in range(2*i,1004000,i):
            num[j] = False


for i in range(n,1004000):
    if i == 1: #1인 경우 2로 예외처리
        print(2)
        break
    if str(i) == str(i)[::-1]: #뒤집어서 같은 경우
        if num[i]: #소수인 경우
            print(i)
            break

 

 

메모

수를 뒤집는 방법을 reversed(), str(i)[::-1] 둘 다 가능하지만

reversed는 list로 변환해줘야 해서 번거로움