BOJ 1747 소수&팰린드롬

LONGNEW·2021년 2월 4일
0

BOJ

목록 보기
141/333

https://www.acmicpc.net/problem/1747
시간 2초, 메모리 256MB
input :

  • n (1 ≤ N ≤ 1,000,000)

output :

  • 조건을 만족하는 수를 출력

일단 소수를 판별해야 하기 때문에 에라토스테네스의 체를 사용해서 소수인 것들을 분류한다.
그리고 이 수들을 이용해서 팰린드롬인지 확인을 하자.
int형 수들을 str형으로 바꿔서 체크를 할 수 있다.

import sys
from math import sqrt

prime_number = [1] * 1004000
prime_number[0] = prime_number[1] = 0
for i in range(2, int(sqrt(1004000))):
    for j in range(i * i, 1004000, i):
        if prime_number[j]:
            prime_number[j] = 0


def palindrome(n):
    n = str(n)
    start = 0
    end = len(n) - 1
    while start < end:
        if n[start] != n[end]:
            return 0
        start += 1
        end -= 1
    return 1

n = int(sys.stdin.readline())
for i in range(n, 1004000):
    if palindrome(i) and prime_number[i]:
        print(i)
        break

n으로 입력이 들어올 뿐 이것은 최대 수의 범위가 아니기 때문에
100만이 들어왔을 떄의 팰린 드롬 수를 찾아서 이 수 까지 포함을 시켜 주어야 한다.
그래서 100만 4천 까지의 범위를 이용했다.

0개의 댓글