BOJ 2023. 신기한 소수 찾기 (DFS)

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

2023번: 신기한 소수

자리 수를 늘려가며 계속해서 소수가 맞는지 확인하는 것이 초점인 문제이다.

첫 자리의 경수 4,6,8,9는 이미 소수가 아니기 때문에 제외하고 2,3,5,7로 시작을 한다.

 

처음 예시

2 - 1 (소수판별) -> 소수가 맞다면 자리수 확장 후 다시 소수 판별... -> N 자리가 될 때까지 (21은 소수가 아니기에 다음은 23을 판별)

231로 확장 되고 231은 소수가 아니기에 다음은 233으로 이런식으로 넘어가게 된다.

 

여기서 재귀의 멈춤 조건은 숫자 확장된 것이 N자리 되는 조건이다. 

N = int(input())

#소수 판별
def isPrime(number):
    for i in range(2, int(number/2) + 1):
        if number % i ==0:
            return False
    return True

def dfs(number):
    if len(str(number)) == N:
        print(number)
    else:
        for i in range(1, 10):
            if i%2 == 0:
                continue
            
            if isPrime(number * 10 + i):
                dfs(number * 10 + i)

dfs(2)
dfs(3)
dfs(5)
dfs(7)