[BOJ]1747 소수&팰린드롬

반응형

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

문제

---

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

입력

---

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

소스코드

n = int(input())
arr = [True] * (1004001)
arr[0] = False
arr[1] = False
for i in range(2, int(1004000 ** 0.5) + 1):
    if arr[i] == True:
        j = 2
        while i * j <= 1004000 :
            arr[i * j] = False
            j += 1

for i in range(n, 1004000):
    if (arr[i] == True) and (str(i) == str(i)[::-1]):
        print(i)
        break
        

해당 문제는 소수판별, 팰린드롬여부 두가지를 체크해야한다.

 

📌소수의 판별여부는 2중 for문을 사용하는 법, n의 제곱근까지의 범위내에서 판별하는 법 등이 있지만 시간복잡도가 가장 낮은에라토스테네스의 체를 사용하여 판별하였다.

 

📌 팰린드롬 check : 뒤집었을 때 원래 문자와 똑같으면 팰린드롬이라 하는데 파이썬의 경우 [::-1]을 사용하면 문자가 거꾸로 뒤집혀 이를 사용하였다.

 

⏰ 회고 : 처음엔 문제의 제한 범위인 1<=n<=1,000,000을 보고 백만까지만 리스트를 생성하였는데 계속틀렸다길래 맞왜틀 시전했는데 입력은 100만까지여도 n보다 큰 소수 출력이 목표이기에 백만보다 큰 소수의 범위까지 리스트 생성을 해줘야한다 !