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

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

예제 입력 1

4

예제 출력 1

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

문제풀이

• 처음 생각했던 풀이는 4자리수면 4자리수 모두를 for loop돌려서 소수를 찾고 소수면 길이를 줄여가면서 줄인 숫자도 소수인지 확인하는 방식으로 구현했다.
• 하지만 이런식으로 구현하면 최악의 경우 10^8 이 걸리기 때문에 시간초과가 발생했다.
• 그래서 https://kimmeh1.tistory.com/353 블로그를 참고했다.
• 신기한 소수가 되는 숫자를 분석해보면 앞자리는 소수만 와야 1자리수가 돼도 소수가 된다.
  • start_list에는 앞자리가 소수가 될 수 있는 수들만 담는다.
• 그리고 마지막자리는 짝수이거나 5면 소수가 될 수 없었다.
  • end_list에는 마지막 자리에서 소수가 될 수 있는 수들을 담는다.
• 이 2가지 사항을 참고하여 문제를 풀면 된다.

제출답안

import math
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000000)


def is_prime_number(x):
    if x == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        return True


def dfs(x, n, end_number):
    if len(x) == n:
        print(x)
        return
    for j in end_number:
        if is_prime_number(int(x + j)):
            dfs(x + j, n, end_number)


def solution():
    n = int(input())
    start_list = ['2', '3', '5', '7']
    end_list = ['1', '3', '7', '9']
    for i in start_list:
        dfs(i, n, end_list)


solution()