DFS

저번에 에라토스테네스의 체의 대해서 이야기 하다가 n이 엄청 크면 메모리가 부족할텐데 어떻게 해결할 것인지에 대한 이야기를 했었다.
그 때는 정답이 뭔지 몰랐는데 이 문제를 보니 알겠다. 백트래킹을 이용한 재귀를 이용해서 자릿수를 하나씩 늘려나가는 것이다.

메모리 제한 : 4MB , 에라토스테네스의 체는 100만 단위까지의 수가 범위일 때는 효과적이지만 그 이상으로 넘어가면 메모리 초과가 발생한다.
그래서 전략을 바꿔서 그때 그때 가능한 수가 아니면 바로 쳐내는(백트래킹) 재귀를 이용했다.

소수가 되려면 , 첫째 자리수는 2, 3, 5, 7( 첫 자리수는 소수) 로 시작해야하고 두번째 자리부터 n번째 자리수 까지는 1, 3, 7, 9로 시작해야한다.
(2의 배수와 5는 소수가 될 수 없음)
이렇게 안하고 첫째 자리수만 맞춰도 되지만, 매우 자주 쓰일 것이니 외울 것!
여기서는 위의 조건을 만족하고, 해당하는 수가 2부터 n의 제곱근까지 돌리면서 나뉘는 수가 없으면 소수이면 뎁스를 늘리면서 뎁스가 n 과 같으면 출력했다.

import math
n = int(input())
#소수 찾기 (2부터 x의 제곱근까지 x로 나뉘는지 확인)
def find_Prime(x):
	if x == 0 or x == 1:
		return False
	for i in range(2, int(math.sqrt(x))+1):
		if x % i == 0:
			return False
	return True
#재귀
def dfs(num, cnt):
	# n자리 까지 모두 소수이면 신기한 소수이다. 출력
	if cnt == n:
		print(num)
		return
        # 두번째 부터 n번쨰 까지는 짝수이면 소수가 될 수 없음 
	for i in [1, 3, 7, 9]:
    		# 자릿수를 늘려가며 소수인지 확인 
		if find_Prime(10*num + i):
			dfs(10*num+i, cnt+1)
#소수가 되려면 첫째 자리는 소수로 시작해야함
for num in [2, 3, 5, 7]:
	dfs(num, 1)