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

 

1990번: 소수인팰린드롬

문제

151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되고 이 두 수가 다르기 때문에 팰린드롬이 아니다. 두 정수 a, b가 주어졌을 때, a이상 b이하인 소수인 팰린드롬을 모두 구하는 프로그램을 작성하시오.

 

 

문제풀이

import sys
input = sys.stdin.readline
#01
def sosu(num):
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True
a,b=map(int,input().split())
#02
if b>10000000:
    b=10000000
#03
arr=[n for n in range(a,b+1) if str(n)==str(n)[::-1]]
for n in arr:
    if sosu(n):
        print(n)
print(-1)

- #01 : 범위가 1억까지이기에, 에라토스테네스의체를 사용하면 시간초과가 발생하기에,

            소수판정 함수를 만들어 소수면 True를 반환, 소수가 아니면 False를 반환한다.

- #02 : 범위는 1억까지지만, b가 1000만 이상일 때 소수인팰린드롬 수는 없기에 

            b의 최댓값을 1000만으로 설정해준다.

- #03 : 소수를 판정하기 전에, 우선 범위인 a~b까지 팰린드롬 수를 먼저 구하여 arr에 저장한다.

           이후 for문을 통해 구한 팰린드롬 수 중에 소수인 수를 출력해준다.

           마지막에는 -1를 출력해준다!