(Python/🥈1)백준리즘알고리즘 1747번 : 소수 펠린드롬

 

문제 바로가기 

 

소수 & 팰린드롬

문제:

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다.

출력:

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

 

풀이:

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n = int(input())

sosu = [True] * (2000001)
sosu[1] = False
m = int(2000000)
for i in range(2,m+1):
    if sosu[i]:
        for j in range(i*2, m+1, i):
            sosu[j] = False
def pel(x):
    x = str(x)
    if x == x[::-1]:
        print(int(x))
        exit()

for j in range(n, 2000001):

    if sosu[j] == True:
        pel(j)

 

백만까지하면 마지막에 99프로에서 틀릴 수도 있으므로 여유롭게 2백만을 줘야한다.

에라토스테네스의 체를 사용하여 소수리스트를 만들어놓고.

 

펠린드롬을 확인하는 함수를 만들어준다.

슬라이싱을 사용했는데, 시간초과가 날 줄 알았지만 나지 않았다.