문제

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

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

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

입력

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

출력

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

오답

에라토스테네스의 체를 이용해서 풀이를 했더니 메모리 초과가 났다..

오답코드

import sys
sys.stdin = open('input.txt')

N = int(input())

INF = 10**N
nums = [True]*INF
nums[1] =False

for i in range(2,INF):
    for j in range(2,(INF-1)//i+1):
        nums[i*j] = False

for i in range(10**(N-1),10**N):
    if nums[i]:
        num = str(i)
        sosu = True
        for j in range(1,N+1):

            k = num[:j]

            if nums[int(k)] ==False:
                sosu = False
                break
        if sosu ==True:
            print(i)

풀이

소수판정을 하는 백트래킹 방법을 이용해서 다시 풀어보았습니다. result가 "" 에서부터 시작해서 한자리씩 더해주면서 소수인지 판단합니다. 뒷자리가 짝수면 어차피 안되니 1,2,3,5,7,9 가 다음으로 올 수 있는 숫자들입니다.
소수를 판단하는 함수는 2부터 그 숫자까지 해도 되지만 그 수의 제곱근까지만 하는 것이 중복을 줄일 수 있습니다. 이 값들을 나누어서 0이 되는게 없으면 소수입니다.

import sys
sys.stdin = open('input.txt')

N = int(input())

nums =[1,2,3,5,7,9] # 마지막 수가 짝수이면 소수가 아니니 빼주는데
                    # 2는 첫자리로는 가능합니다.
def dfs(strnum):
    if len(strnum)==N:      # N자리 숫자면
        print(strnum)  # 출력을 해줍니다.
        return          # 함수 끝

    for n in nums:             # 1,2,3,5,7,9 들을
        newnum = strnum + str(n) # 하나씩 뒷자리로 넣어봅니다.
        if sosu(int(newnum)):   # 이숫자가 소수인지 판단해봅니다.
            dfs(newnum)         # 소수이면 dfs로 들어갑니다.


def sosu(num):  # 소수 판단하기
    if (num==1): # 1은 소수가 아닙니다
        return False
    for i in range(2, int(num**0.5) +1):    #2부터 num의 제곱근까지
        if num%i ==0:       #  하나씩 나눠보다가 나눠지는 값이 있으면
            return False    # 소수가 아닌것
    return True             # 다 통과하면 소수
dfs("")