[백준][Python] 1747번 소수&팰린드롬

1747번: 소수&팰린드롬

 

코드

import math

N = int(input())

def prime(N):
    for i in range(2,int(math.sqrt(N))+1):
        if N%i == 0:
            return False
    return True
ans = 0
for i in range(N,1000001):
    if i>1 and str(i) == str(i)[::-1]:
        if prime(i):
            print(i)
            ans = 1
            break
if ans == 0:
    print(1003001)

 

설명

원래 소수를 구할 때 에라토스테네스의 체를 사용하려고 했는데 이거는 팰린드롬인 수 중에서 소수인 것을 찾는 것이기 떄문에 굳이 모든 소수를 구하지 않아도 된다고 생각했다.

그래서 제곱근을 사용해서 2부터 (해당 수의 제곱근 + 1)까지의 수 중 0으로 나누어 떨어지는 수가 없으면 소수라고 판별했다.

팰린드롬의 수인지 확인하기 위해서 입력받은 수를 문자열로 변환시켜줬고, [ : :-1]을 써서 역순으로 만들어서 원래 수와 같은지 비교했다.

그리고 만약 1000000 이하의 숫자에서 팰린드롬인 수가 나오지 않았다면 1003001을 출력하게 해줬다. 입력받을 수 있는 최대 수가 1000000이고, 이 수를 넘는 가장 작은 팰린드롬 수가 1003001이기 때문이다.

또, 1을 입력받을 경우도 있기 때문에 if문에 i가 1보다 큰 조건을 추가해줬다.