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

🤔문제 해결

• G5 | 에라토스테네스의 체, 문자열

소수를 찾고, 그게 소수이면 팰린드롬인지 확인한다.

팰린드롬인지 확인하는 법은 간단하다.

문자를 뒤집어서 같으면 True

브루트포스로 찾아도 문제해결은 가능하지만 에라토스를 쓰는것과 시간이 10배 이상 차이난다.

 

1. 에라토스테네스의 체를 써서 제한 숫자까지 소수들을 구해놓는다.
2. 그 소수이면서 팰린드롬이면 값을 반환하고 끝

💻소스 코드

def make_eratos(l: int) -> list:
    eratos = [1] * (l + 1)
    eratos[0], eratos[1] = 0, 0
    for i in range(2, l):
        if eratos[i]:
            for j in range(i * 2, l, i):
                eratos[j] = 0
    return eratos


def is_palindrome(n: int) -> bool:
    s = str(n)
    if s == s[::-1]:
        return True
    return False


if __name__ == '__main__':
    N = int(input())

    # 100만이 넘어가는 첫 소수는 1003001
    limit = 1003001
    prime = make_eratos(limit)

    for num in range(N, limit + 1):
        # 1. 소수인지 판별한 후
        # 2. 팰린드롬인지 판별하기
        if prime[num] and is_palindrome(num):
            print(num)
            break
    else:
        print(1003001)
 

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

1747번: 소수&팰린드롬