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

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

소수를 구해야 하므로 '에라토스테네스의 체'를 이용하여 소수 판별

팰린드롬인 수를 구하기 위해 10으로 나눈 나머지 및 몫을 이용해 숫자 역으로 배치하여 판별

2) 알고리즘

• 에라토스테네스의 체

3) 풀이 코드

사용 언어 - Python

import sys


N = int(sys.stdin.readline())               # 특정 숫자
prime_num = [1] * 1003002                   # 정답이 나올 수 있는 최대 숫자까지만 리스트 생성
prime_num[0] = prime_num[1] = 0             # 0, 1은 소수가 아니므로

for i in range(2, int(1003002**0.5) + 1):   # 에라토스테네스의 체
    if prime_num[i]:
        mul = 2
        while mul * i < 1003002:
            prime_num[i*mul] = 0
            mul += 1

idx = 0                                     # 특정 보다 얼마나 큰지 결정할 변수
while True:
    reverse_num = 0                         # 앞뒤가 바뀐 숫자를 저장할 변수
    num = N + idx                           # 특정 수보다 idx 크기만큼 큰 수

    if prime_num[num]:                      # 지금 숫자가 소수라면
        while num:                          # 숫자를 거꾸로 만들어서 저장
            reverse_num = (reverse_num * 10) + (num % 10)
            num //= 10

        if reverse_num == N + idx:          # 숫자를 거꾸로 해도 같다면
            print(reverse_num)              # 출력 및 종료
            break

    idx += 1

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다

2) 새롭게 학습한 내용

특별히 없습니다

---

🔗 문제 링크

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

1747번: 소수&팰린드롬

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다