I am developing person.

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

import math

N = int(input())

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

prime = [2,3,5,7]; odd = [1,3,5,7,9]

def result(cnt, num):
    if cnt==N: print(num)
    for i in odd:
        x = num*10+i
        if isPrime(x): result(cnt+1,x)

for i in prime: result(1,i)

point 1

왼쪽부터 1, 2, …, N자리가 모두 소수인 숫자는 신기한 소수이다. N이 주어졌을 때, N자리의 신기한 소수를 구해야 한다. 이때, 가장 높은 자리 수는 소수여야하며, 가장 낮은 자리 수는 홀수여야한다. 또한, 그 사이의 값들도 왼쪽부터 1, 2, 3, … N자리를 따졌을 때 가장 낮은 자리에 위치하는 경우가 생기므로, 홀수여야한다.

soltion

point1의 고찰에서, 한 자리 수 소수를 담은 리스트 prime과 한 자리 수 홀수를 담은 리스트 odd를 만들었다.

for i in prime : result(1,i)

위 코드에서, prime 리스트 안의 숫자를 하나씩 첫 자리수로 넣으며 result 함수를 호출한다. result 함수에서는, 재귀적으로 모든 N자리수 소수를 구하게 되는데,

x = num*10+i
if isPrime(x) : result(cnt+1, x)

현재 숫자에 해당하는 num에 10을 곱해 한 자리수를 뒤로 미룬 후, odd 안의 원소를 가장 낮은 자리수로 하여 새 수를 만든다. 만들어진 수가 소수라면, cnt(자리수를 나타내는 변수)+1하여 자릿수를 하나 늘이고, 새로 만들어진 수인 x를 num 자리에 넣어 result 함수를 재호출한다. 이 때 cnt가 N인 소수가 만들어졌다면 출력한다.

참고