[백준/1747] 소수&펠린드롬 (Python)

Problem : 1747번: 소수&팰린드롬 (acmicpc.net)

1747번: 소수&팰린드롬

Difficulty : Silver 1

Status : Solved

Time : 00:07:35

 

---

 

 

문제 설명

 

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

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

 

 

입력 및 출력

 

입력

첫째 줄에 N이 주어진다.

 

출력

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

 

입력 예시

31

 

출력 예시

101

 

 

---

 

 

풀이

 

소수이자 펠린드롬을 찾는 알고리즘. n에 1을 무한히 더해가며 소수이자 펠린드롬일 경우 출력하면 된다. 단일 숫자의 소수 판정에는 최소 O(logN)이 소모되므로 펠린드롬인지 먼저 검사한 후 맞다면 소수를 검사하는 게 더 효율적일 것이다. 에라스토테네스의 체를 사용하려면 먼저 최대 입력값인 1000000보다 큰 소수이자 펠린드롬을 구한 후 판정해야하므로, 조금 더 접근이 어려울 수 있겠다.

 

 

n = int(input())

def is_prime_num(num) :
  for i in range(2, int(num ** 0.5)+1) :
    if num % i == 0 :
      return False
  return num != 1

def is_palindrome(num) :
  num = str(num)
  return num[::-1] == num

while True :
  if is_palindrome(n) and is_prime_num(n) :
    print(n)
    exit()
  n += 1

풀이 완료!