[백준1747] 소수&팰린드롬

www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

---

풀이

 

문제에서 요구하는대로 N보다 큰 소수를 찾고 그 소수리스트 중 팰린드롬 수를 찾으면 된다.

 

소수를 찾는 방법은 에라토스테네스의 체를 참고한다

 

에라토스 테네스의 체는 간단히 설명해서 1~N까지 반복하면서 배수들을 모두 제거하는 것이다.

 

소수는 어떤 숫자의 배수가 아니기 때문이다.

 

이렇게 소수리스트를 만든 후 찾는 범위의 숫자 중 작은것부터 하나씩 뽑아 팰린드롬인지 검사한다.

 

---

시간복잡도

 

에라토스테네스의체가 시간복잡도를 지배한다.

 

에라토스테네스의 체는 복잡한 과정을 거쳐 O(NloglogN) 가 나온다고 한다.

 

---

코드

N=int(input())

prime = []
is_prime = [0]*(2000000)
is_prime[0]=1
is_prime[1]=1
for i in range(2,2000000):
    if is_prime[i]:
        continue
    else:
        for j in range(i*i,2000000,i):
            is_prime[j] = 1

def p(n):
    t = str(n)
    if t == t[::-1]:
        return True
    return False

for i in range(N,2000000):
    if is_prime[i] == 0 and p(i):
        print(i)
        break