[백준] 10859번 뒤집어진 소수

💡문제접근

• 일반적인 소수 판정 알고리즘을 사용해 문제를 해결했다.
• N의 값의 범위는 1 ≤ N ≤ 1e+16이므로 나의 로직대로 선형탐색을 진행하면 Python3에서 시간초과가 발생할 수 밖에 없다. 그래서 같은 논리지만 PyPy3로 제출했더니 AC를 받았다.

💡코드(메모리 : 114328KB, 시간 : 2004ms, PyPy3로 제출)

import sys
input = sys.stdin.readline
def isPrime(x):
    if x == 1 or x == 0:
        return False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

N = int(input())
if N == 2 or N == 5:    # 2, 5는 뒤집혀서도 2, 5 그대로 소수이므로 yes
    print("yes")
    exit(0)
if '3' in str(N) or '4' in str(N) or '7' in str(N):     # 3, 4, 7은 뒤집히면 더 이상 숫자가 아니므로 no
    print("no")
    exit(0)
if isPrime(N):  # 입력값 N이 소수이면?
    t = list(str(N))[::-1]
    for i in range(len(t)):
        if t[i] == '6': # 6을 뒤집으면 9가 된다.
            t[i] = '9'
        elif t[i] == '9': # 9를 뒤집으면 6이 된다.
            t[i] = '6'
    t = int(''.join(t))
    if isPrime(t):  # 뒤집은 수 역시 소수이면?
        print("yes")
    else:           # 뒤집은 수가 소수가 아니라면?
        print("no")
else:   # 입력값 N이 소수가 아니라면?
    print("no")

💡소요시간 : 11m