[Python 파이썬]백준 1990번 소수인팰린드롬 풀이

백준 1990번 소수인팰린드롬 문제다.

소수 문제를 보면 항상 에라토스테네스의 체가 먼저 떠오르는데,

뭔가 에라토스 테네스의 체 하면 정석으로 떠오르는

primes = [False, False] + [True] * (n-1)
for i in range(2, n+1):
	if primes[i]:
    	print(i)
    	for j in range(2*i, n+1, i):
        	primes[j] = False

로 풀면 배열 길이가 1억 개라서 많이 힘들다... (시간 초과도 시간 초과고 메모리 초과도 나올 거 같다...)

아니 아무튼 이걸로 한 번 돌려보면

소수로 팰린드롬을 이루는 경우 중에 자릿수가 짝수인 팰린드롬 소수는 '11' 밖에 존재하지 않는다(?)는 걸 알 수 있는데 이걸로 범위를 확 줄여줄 수 있다.

n, m = map(int, input().split())
if m >= 10000000:
    m = 10000000
if 1000000 >= m >= 100000:
    m = 100000
if 10000 >= m >= 1000:
    m = 1000

수의 자릿수가 짝수면 그냥 그 자릿수의 최솟값으로 바꿔줬다.

여기까지해서 배열 길이를 10,000,000개로 줄인다고해도 당연히 시간초과가 난다.
(어지간한 문제는 거의 100만 개 내외로 해야하는 듯하다..)

근데 소수가 다 그렇지만 짝수라고는 '2' 밖에 없다.

• 그럼 굳이 에라토스테네스의 체를 구현할 때 '짝수번째 원소를 넣어야하나?' 라는 의문이 생길지도..?

primes = [False] + [True] * (m//2)
for i in range(1, len(primes)):
    if primes[i]:
        print(2*i+1)
        for j in range(i + (2*i+1), len(primes), 2*i+1):
            primes[j] = False

아무튼 이렇게 하면 2를 제외하고는 배열 길이를 절반으로 줄이고 소수를 모두 구할 수 있다.

이제 여기에 팰린드롬 검사만 넣어주자.

코드

def reverse(text):
    result = ''
    for t in text:
        result = t + result
    return result


n, m = map(int, input().split())
if m >= 10000000:
    m = 10000000
if 1000000 >= m >= 100000:
    m = 100000
if 10000 >= m >= 1000:
    m = 1000

primes = [False] + [True] * (m//2)
for i in range(1, len(primes)):
    if primes[i]:
        if i*2 + 1 >= n and str(i*2+1) == reverse(str(i*2+1)):
            print(2*i+1)
        for j in range(i + (2*i+1), len(primes), 2*i+1):
            primes[j] = False
print(-1)

이렇게 풀면 끝 !