문제
N 이상인 수 중 소수이면서 팰린드롬인 가장 작은 수를 구하라.
입력
정수 N이 주어진다 (1 이상 1,000,000 이하).
출력
N 이상이면서 소수이고 팰린드롬인 가장 작은 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
31 | 101 |
풀이
N부터 시작하여 소수이면서 팰린드롬인 수를 찾을 때까지 증가시킨다.
- 소수 판별: 2부터 sqrt(n)까지 나누어 확인한다
- 팰린드롬 판별: 문자열로 변환 후 뒤집은 것과 비교한다
- 두 조건을 모두 만족하면 출력하고 종료한다
핵심 아이디어: 팰린드롬 소수의 간격이 크지 않으므로, N부터 순차 탐색해도 충분히 빠르다.
코드
n = int(input())
def isPrime(n):
if n == 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def isPalindrome(n):
if str(n) == str(n)[::-1]:
return True
return False
while True:
if isPalindrome(n) and isPrime(n):
break
n += 1
print(n)복잡도
- 시간: O(N²)
- 공간: O(N)