[백준] 소수&팰린드롬

문제

https://www.acmicpc.net/problem/1747

TC

is_prime(): O(sqrt(n))

Idea

n의 범위가 1 <= n <= 1,000,000이기 때문에 하나하나 순서대로 소수인지 확인하면 시간초과 결과를 받을 것이다.

에라토스테네스의체 또는 제곱근까지만 따져보는 방법을 사용해야 한다.
팁 아닌 팁이자면 팰린드롬 수를 먼저 구하면 시간복잡도가 크게 줄을 것이다.

code (Python)

def is_prime(n):
    # 1은 소수가 아님
    if n <= 1:
        return False
    # n의 제곱근까지 살펴보면서
    for i in range(2, int(n**0.5)+1):
        # 나뉘는 수가 있다면 소수가 아님
        if n % i == 0:
            return False
    return True

def is_palindrome(n):
    # 팰린드롬이라면 true
    return str(n) == str(n)[::-1]

# 입력으로 주어진 수
n = int(input())

while True:
    # n보다 크거나 같은 수 중에서, 소수이면서 팰린드롬인 수가 있다면 출력하고 종료
    if is_palindrome(n) and is_prime(n):
        print(n)
        break
    n += 1

self code review

소수를 구하는 함수에서 제곱근까지 for문이 돌리는게 좋으려나, 에라토스테네스의 체 방식을 사용하는게 좋으려나 고민 좀 해보았다.

그리고 꿀팁 아닌 팁이라면, 소수를 구하는 함수와 팰린드롬을 구하는 함수 중
팰린드롬을 구하는 함수를 먼저 작성하여 수를 걸러낸 후, 소수를 구하는 것이 시간복잡도를
훨~씬 줄일 수 있다.
why? 팰린드롬 수 < 소수이기 때문!