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

 

 

 

 

 

 

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

1747번: 소수&팰린드롬

 

 

 

🔥 문제 풀이

 

문제를 처음 읽고 n의 범위가 너무 크지만, 소수이면서 가장 작은 팰린드롬 숫자를 찾는 것이기 때문에

while 문을 통해서 n을 1씩 증가하면서 소수인지 && 팰린드롬 숫자인지 확인해주면 된다고 생각했다.

 

그래서 isPrime 함수를 만들어 소수인지 확인하고, 소수라면 팰린드롬 숫자인지 확인할 수 있도록 구현해줬다.

 

 

👀 위에서 설명한 대로 구현했을 때, 시간이 생각보다 오래 걸렸다.  그래서 시간을 단축시킬 수 있는 방법을 찾아봤음! 

-> 소수의 개수 보다 팰린드롬의 개수가 더 많으므로 팰린드롬 숫자인지 먼저 확인한 후에 소수인지 확인하면 실행 시간이 확 줄어든다! 

 

 

 

import sys, math
input = sys.stdin.readline
 
def isPrime(num):
    if num == 1:
        return False
 
    for i in range(2, int(math.sqrt(n)) + 1):
        if num % i == 0:
            return False
 
    return True
 
def isPalindrome(num):
    if str(num) == str(num)[::-1]:
            return True
    return False
 
 
n = int(input())
 
while True:
    if isPalindrome(n):
        if isPrime(n):
            print(n)
            exit(0)
    n += 1