[BOJ/백준] 2023 신기한 소수

N = int(input())
def makePrimeNumber(num,idx):
    if idx == N:
        result.append(num)
    else:
        for last_num in range(1,10,2):
            new_num = num*10 + last_num
            if isPrime(new_num):
                makePrimeNumber(new_num,idx+1)

def isPrime(num):
    if num in prime_numbers:
        return True
    for i in range(2,int(num**0.5)+1):
        if num%i == 0:
            return False
    prime_numbers.add(num)
    return True


prime_numbers = set([2,3,5,7])
result = []


for num in [2,3,5,7]:
    makePrimeNumber(num,1)
result.sort()

for row in result:
    print(row)

이 문제는 처음에 모든 N자리의 숫자를 primnumber 인지를 구했더니 메모리초과가 났던 문제이다.

 

이 문제를 푸는 방법은 다음과 같다.

 

이 문제를 보면 우리는 제일 왼쪽부터 한자리숫자씩 늘리면서 모든 경우에 소수인 것을 구하는 것이다.

 

그러면 우리가 한자리숫자에서 소수인 것은 2,3,5,7 임을 알 수 있다.

 

그러면 제일 왼쪽은 무조건 2,3,5,7로 시작되게 해준다.

 

그리고 N자리를 dfs로 구해주면 된다.

 

현재 num에 10을 곱하고 끝자리를 바꿔가면서 그 값이 소수인지 판별해주면 된다.

 

그리고 우리는 한자리숫자를 제외한 두자리숫자부터는 끝 숫자부분이 홀수여야지만 소수가 될 가능성임을 알 수 있다.

 

그러므로 끝자리는 홀수들만 들어가게 해준다.

 

소수를 판별하는 방법은 이 수의 제곱근까지의 숫자까지 나눠가면서 나눠지는 경우가 있는지 확인해주면 된다.

 

그리고 한번 소수로 판별된 경우에는 두번 탐색할 수고를 덜기 위해, set에 저장해준다.

 

위와 같은 방식으로 N자리 숫자를 만들고

 

정렬 한뒤에 출력하면 된다.