[BOJ/python] 2023번 신기한 소수

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

2023번: 신기한 소수

 

문제 해석

 

왼쪽 부터 1자리, 2자리, 3자리, 4자리 순으로 n이 주어지면 n자리 까지의 모든 수가 소수인 수를 구하는 문제이다.

---

코드

def go(t):
	# 소수 체크 #
	flag = True
	i = 2
	while i * i <= t: 
		if t % i == 0:
			flag = False
			break
		i += 1

	if flag: # 소수가 참일 때 현재 소수 * 10 + i를 하여 다시 체크
		for i in range(1,10):
			go(t*10 + i)
	else: return # 거짓일 때 return

	# -------------------- #

	# m자리가 될 때 출력
	if len(str(t)) == m:
		print(t)
		return
		
m = int(input())
for i in range(2,10):
	go(i)

---

문제 풀이

 

백트래킹을 사용하여 푸는 방법을 생각해보았다.

첫째 자리부터 2부터 9까지 재귀함수에 대입하여 소수 판별을 한 후 다음 자리수를 하나씩 대입하여 소수 판별을 하면 된다.

 

먼저 소수 판별하는 방법은 2 ~ n-1 까지의 수를 나누어 보았을때 나머지가 없어야 한다.

하지만 이 방법으로는 시간복잡도가 O(N) 이 되기때문에, 훨씬 시간이 적게 드는 방법을 사용했다.

2 ~ √(n-1) 까지만 나누어보아도 소수 판별이 가능하다.

 

재귀함수 go(t)를 해석하면

먼저 소수를 판별한다. 루트를 사용하면 표기상 불편하기 때문에 i*i 을 사용했다.

소수가 맞다면 flag = True값이 되고, 다음 for문을 통해  t * 10 + 1 ~ 9 까지 들어가게 된다.

#( 0을 넣으면 2로 나누어지기 때문에 1부터 넣었다. )

이후 문제에서 원하는 m자리 까지 도달하면 출력한다.

 

m자리를 받고 반복문을 통해 2 부터 9까지 수를 넣었다.

#( 0과 1은 재귀함수가 아니기 때문에 2부터 넣었다. )

 

원문

https://ddingmin00.tistory.com/22

[BOJ/python] 2023번 신기한 소수