[알고리즘] 백준 1747 파이썬 - 소수&팰린드롬

 

1747번: 소수&팰린드롬

 

 

문제

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

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

 

 

 

문제풀이

import sys
input = sys.stdin.readline
n=1003001
ans=[]
#01
arr=[False, False]+([True]*(n-1))
for i in range(2,n+1):
    if arr[i]:
        ans.append(str(i))
    for j in range(i*2,n+1,i):
        arr[j]=False
x=int(input().rstrip())
#02
for i in range(len(ans)):
    if(int(ans[i])>=x):
        rev=ans[i][::-1]
        if(ans[i]==rev):
            print(ans[i])
            quit()

 

- 문제를 잘 읽어야한다. 어떤 수 n이 1,000,000까지 입력을 받을 수 있다. 

  즉 1,000,000을 입력받았을 때 문제를 만족하는 값은 1,003,001이다. 

  그렇기에 1,003,001까지 에라토스테네스의 체를 통해 소수를 구한다.

- #01 : 에라토스테네스의 체를 사용하여 ans에 1,003,001까지의 소수를 추가한다.

           (에라토스테네스의 체의 설명은 아래 링크를 참조)

[알고리즘] 백준 17103 파이썬 - 골드바흐 파티션(에라토스테네스의 체)

- #02 : ans의 길이는 대략 8만 정도로 위의 에라토스테네스의 체의 시간과 합쳐도

           충분히 시간 안에 문제를 풀 수 있다.

           만약 소수 ans[i]값이 x보다 크거나 같으면 ans[i] 값과 그 리버스 값이 같다면

           그 값을 출력하고 코드를 종료한다.