[Python] BOJ 2023 - 신기한 소수

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

2023번: 신기한 소수

# 처음에 에라토스테네스의 체를 사용해서 N자리의 모든 수에 대한 소수판정 배열을 만들어서

   제출했는데, 메모리초과가 발생했다. 다시 문제제한을 보니 메모리제한이 4MB로 매우 작다는 것을

   발견했다.. 

 

 

# 따라서 각 자리수마다 숫자를 붙여가며 재귀함수를 돌려서 해결하였다.

   어차피 맨 왼쪽 첫번째자리수 역시 소수여야 하므로 처음에 2,3,5,7로 첫번째자리를 시작하면 된다.

   2,3,5,7 뒤에 짝수가 오면 소수가 절대 될 수 없으므로 1,3,5,7,9를 하나하나 붙여가며 tmp에 넣어준다.

   prime(tmp)로 tmp가 소수인지 확인해주고 소수이면 BT(tmp)로 재귀적으로 BT함수를 실행한다.

 

   BT함수를 계속 실행하다 n의 길이가 N(우리가 구하고자하는 자리수)와 같아지면 n을 출력하고

   함수를 종료한다.

 

import math
def prime(n):
    if n == 0 or n == 1:
        return False
    for i in range(2, int(n**(1/2)) + 1):
        if n % i == 0:
            return False
    return True

def BT(n):
    if len(str(n)) == N:
        print(n)
    else:
        for i in range(1, 10, 2):
            tmp = n * 10 + i
            if prime(tmp):
                BT(tmp)

N = int(input())
for i in [2, 3, 5, 7]:
    BT(i)

(solved.ac 티어: 골드 5)