[BOJ] 1747. 소수&팰린드롬(Python)

1747번: 소수&팰린드롬

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

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

• 사용 알고리즘 : 소수판별 알고리즘(제곱근까지 구함)
• N을 1씩 늘려가며
• 팰린드롬이고 소수인 조건을 만족시키는 즉시 반복문 탈출, 그 때의 N 출력
• isPalindrome() 함수에서 팰린드롬 판단
  • 절반 길이만큼 돌리면서 맨 앞 숫자, 맨 뒤 숫자 매칭해가며 다르면 바로 False 리턴 끝까지 마치면 True 리턴
• isPrimeNumber() 함수에서 소수인지 판단
  • 1이면 소수 아님
  • 2 이상인 숫자부터 N의 제곱근까지 i를 늘려가며 N이 i로 나누어 떨어진다면 1이외의 다른 약수가 존재한다는 의미이므로 리턴 False, N의 제곱근까지 나누어 떨어지는 숫자가 없다면 리턴 True

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

def isPalindrome(n):
    length = len(n) // 2
    for i in range(length):
        if n[i] != n[-i-1]:
            return False
    return True

def isPrimeNumber(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if not n%i:
            return False
    return True

# main
N = int(input())
while True:
    if isPalindrome(str(N)) and isPrimeNumber(N):
        break
    N += 1
print(N)

---

• 시간 : 156ms / 메모리 : 123340kb
• 고찰 : 오랜만에 소수 문제를 풀어봤다! 문자열 더 더 열심히 하자.