[python] 백준 2023 신기한 소수

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

2023번: 신기한 소수

 

 

 

 

문제 풀이

• 두자리 이상일때(n≥2) 맨 앞자리는 소수만 가능(2,3,5,7) 나머지 자리는 홀수만 가능(1,3,5,7,9)
• 그래서 앞자리 만드는 것 부터 시작.(2, 3, 5, 7)
• 그 다음 수를 이어 붙일 때 소수인지 확인하고 소수이면 이어붙이고 아니면 다른 수 찾기
• n자리 수가 되었을 때 출력
• 전형적인 DFS로 풀 수 있다.

CODE

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def is_prime(num):
    if num%2 ==0:
        return False
    for i in range(3,int(num/2)+1,2):
        if num%i ==0:
            return False
    return True

def DFS(num):
    if len(str(num)) == n:
        print(num)
        return
    else:
        for i in range(1,10,2):
            if is_prime(num*10+i):
                DFS(num*10+i)
if __name__=='__main__':
    n = int(input())
    DFS(2)
    DFS(3)
    DFS(5)
    DFS(7)