소수&팰린드롬

처음 생각한 전략

1) 소수판별 데이터 만들기: 에라토스테네스의 체 100만개 만들기
2) 팰린드롬 판별: 소수조건 만족하는거는 list로 변경해서 reverse()시켜서 비교

# 소수&팰린드롬
import math
import sys
input = sys.stdin.readline
def check(data):
    v1 = list(str(data))
    v2 = v1.copy()
    v2.reverse()
    if v1==v2:
        return True
    else:
        return False
m = 1000001
n = int(input())
prime=[True]*(m)
prime[0]=False
prime[1]=False
for i in range(2, int(math.sqrt(m))+1):
    if prime[i]==False:
        continue
    for j in range(2*i, m, i):
        prime[j] = False

for i in range(n, m):
    if prime[i]==True:
        if check(i):
            print(i)
            break

But 문제 발생 Where?

어떤 수 N(1<=N<=1,000,000)이라 백만이 N이 되면 백만이 넘어가는 소수값이 팰린드롬이 되어야 하는데 검사를 백만까지만 해서 아무것도 출력이 안됨

해결방법

자료형을 200만까지 늘렸다.

m = 2000000

최적화(투 포인터 활용)

reverse()시켜서 비교하면 O(n) + O(n) 즉 O(n)만큼으 시간복잡도가 걸린다.
그러나 투포인터를 활용하면,
1) 공간복잡도 절약: 새로운 reverse 자료형 안만들어도됨
2) 시간복잡도 절약: 반만 비교하면됨(n/2) + 밖에서부터 안쪽으로 비교하다가 한번이라도 아니면 중간에 멈춤
O(n)이어도 이정도까지 절약 가능...

# 소수&팰린드롬
import math
import sys
input = sys.stdin.readline
def check(data):
    v1 = list(str(data))
    answer = True
    start_point=0
    end_point = len(v1)-1
    while start_point<end_point:
        if v1[start_point] != v1[end_point]:
            answer = False
            break
        start_point+=1
        end_point-=1

    return answer
m = 2000000
n = int(input())
prime=[True]*(m)
prime[0]=False
prime[1]=False
for i in range(2, int(math.sqrt(m))+1):
    if prime[i]==False:
        continue
    for j in range(2*i, m, i):
        prime[j] = False

for i in range(n, m):
    if prime[i]==True:
        if check(i):
            print(i)
            break