[2023] 신기한 소수(DFS, 백트래킹)

2023번: 신기한 소수

 

분석

1. 자리수가 한 개인 소수 2,3,5,7부터 탐색 시작
2. 자릿수가 두개인 현재수*10+a를 계산하여 소수인지 판단, 소수라면 재귀 함수로 자릿수를 하나 늘림
   • a가 짝수인 경우는 항상 2를 약수로 가지므로 가지치기로 a가 짝수인 경우 제외
3. 자릿수를 n까지 확장했을 때 그 값이 소수라면 해당 값 출력

 

풀이

"""
소수 7331 : 733, 73, 7 소수 (왼쪽부터 1,2,3,4 자리 모두 소수)
n(1~8)자리 숫자 중 신기한 소수 찾기
"""
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
n = int(input())

# 소수판별
def isPrime(num): # 단순소수판별 함수 사용해도 시간안에 가능
    for i in range(2, int(num/2+1)):
        if num%i==0:
            return False
    return True


def dfs(x):
    if len(str(x))==n:
        print(x)
    else:
        for i in range(1,10): # 뒷자리 수 탐색
            if i%2==0: # 짝수인 경우 탐색 불필요
                continue
            # 1,3,5,7,9
            if isPrime(x*10+i): # 소수인경우
                dfs(x*10+i)

# 일의 자리 소수는 2,3,5,7이므로 4가지 수에서만 시작
dfs(2)
dfs(3)
dfs(5)
dfs(7)