[백준/파이썬] 2023: 신기한 소수

문제 보러가기!!

N 자리 신기한 소수를 찾는 문제이다. 신기한 소수란, 왼쪽에서부터 첫째자리만 봐도 소수이고, 첫째 둘째 자리를 봐도 소수이고, 1-3자리를 봐도 소수이고, ... 1-N자리를 봐도 소수인 수이다. 예를 들어서, 2393은 2도 소수, 23도 소수, 239도 소수, 2393도 소수이다!

N은 최대 8이니까 크기가 9인(0번째 인덱스는 편의를 위해서 안 씀) 2차원 리스트를 만들었다.

1 자리 신기한 소수는 쉽게 구할 수 있으니 미리 구해서 첫번째 리스트에 넣었다. 2, 3, 5, 7

그 이후부터는 N자리 신기한 수까지 차례 차례 신기한 수를 찾았다.
방법은 다음과 같다. 2자리 신기한 소수를 찾으려면 왼쪽에 1자리 소수를 두고, 오른쪽에 한자리 수를 붙인 뒤에 그 수가 소수인지 확인하면 된다. 3자리 신기한 소수를 찾으면 왼쪽에 2자리 소수를 두고, 오른쪽에 한자리 수를 붙인 뒤에 그 수가 소수인지 확인하면 되고! (check_sosu 함수) 2중  for문으로 쭉 ~ 봤다.

그 후에 N번째 신기한 소수들을 찾으면 정렬해서 출력하면 된다 !

import sys

input = sys.stdin.readline

N = int(input())

sosus = [[0] for _ in range(9)]

sosus[1].extend([2, 3, 5, 7])


def check_sosu(num: int) -> bool:
    for k in range(2, int(num ** 0.5) + 1):
        if num % k == 0:
            return False
    return True


for i in range(2, N + 1):
    for j in sosus[i - 1]:
        if j == 0:
            continue
        for k in range(1, 10):
            if k == 0:
                continue
            tmp1 = int(str(j) + str(k))
            if check_sosu(tmp1):
                sosus[i].append(tmp1)

answer = sorted(list(set(sosus[N])))
for i in range(1, len(answer)):
    print(answer[i])