백준 2023 신기한 소수

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

2023번: 신기한 소수

와 이전에 풀때 포기했던 문젠데, 백트래킹을 해보고 왔더니 정말 쉬운 문제였다.

먼져, 첫자리는 소수여야하므로 2,3,5,7이외의 수는 없다.

2,3,5,7을 시작으로 하는 n자리의 숫자를 찾으면 되는데,

한단계씩 지나갈때마다 그 단계의 신기한 소수판별을 하고, 아니면 더이상 탐색하지 않는다.

신기한 소수를 판별할 때, 그 자리만 판별한다.

ex 길이가 3일때, 길이가 1,2인 경우는 앞에서 했으므로, 3인 경우만 판별하면 끝

기분좋게푼 문제였다.

def check(strnum):
    num=int(strnum)
    if num%2==0: return False
    for i in range(3,int(num**0.5)+1,2):
        if num%i==0:
            return False
    return True

first=['2','3','5','7',]
def dfs(strnum): # str
    if len(strnum)==n:
        print(strnum)
        return

    for i in (1,3,5,7,9):
        tmp=strnum+str(i)
        if check(tmp):
            dfs(tmp)


n=int(input())
for start in first:
    dfs(start)