[백준] 1990번 소수인팰린드롬

💡문제접근

• 계속되는 메모리초과로 인해서 어떻게 하면 줄일 수 있는지 고민을 많이 했다.
• 5 ≤ A ＜ B ≤ 100,000,000의 범위가 주어졌는데 이 때 10,000,000이상 100,000,000이하의 범위에서는 소수도 존재하지 않고 팰린드롬도 존재하지 않게 된다는 것을 알 수 있다. 이 사실을 이용해서 메모리초과를 피할 수 있었다.
• 범위가 넓은 경우 에라토스테네스의 체를 사용하는 것보다 직접적인 소수 판별 알고리즘을 사용하는 것이 훨씬 좋을 수 있을 것 같다.

💡코드(메모리 : 109380KB, 시간 : 4064ms)

import sys
input = sys.stdin.readline

def palindrome(x):
    x = str(x)
    if x == x[::-1]:
        return True
    return False

A, B = map(int, input().strip().split())
# 10,000,000보다 큰 수 중에서는 소수이면서 팰린드롬인 수가 존재하지 않는다.
if B > 10000000:
    B = 10000000
arr = [True] * (B+1)
arr[0] = False
arr[1] = False
for i in range(2, B+1):
    if arr[i]:
        for j in range(i*i, B+1, i):
            arr[j] = False

for i in range(A, B+1):
    if arr[i] and palindrome(i):
        print(i)
print(-1)

💡소요시간 : 10m