[백준] 2023번: 신기한 소수

🧩문제 해석

자리수 n이 주어졌을 때 그 n 자리수인 신기한 소수를 출력하는 문제
신기한 소수란 
n = 4 일 경우
num[0] 도 소수
num[:2] 도 소수
num[:3] 도 소수
num 도 소수라면 num은 신기한 소수이다. 
즉 첫번째 숫자도, 첫번째부터 두번째숫자도, ... 첫번째부터 n번째숫자도 소수라면 신기한 소수인 것이다.

 

 

🔍 고민

모든 숫자를 대입해가며 소수인지 판별한다면 시간초과가 날게 뻔했다. (요즘 시간초과가 많이 난다...ㅎ)
예제 문제를 보니 알 수 있는 점이 있었다. 첫번째 숫자는 무조건 2,3,5,7 이고 그 다음에 오는 숫자들은 1,3,7,9 들이 막 조합되어서 나타났다. 돌려볼 숫자들이 절반이상 줄어들었다!

 

첫번째 숫자가 2, 3, 5, 7 인 이유!

어찌보면 당연한 이야기이다. 신기한 소수가 되려면 제일 첫번째 숫자도 소수여야 하니 당연히 첫번째 숫자는 소수인 2, 3, 5, 7 밖에 오지 못한다.

 

 

다음 숫자들이 1, 3, 7, 9 인 이유!

끝자리가 0, 2, 4, 6, 8이면 2로 나누어지기 때문에 소수가 되지 못한다. 그리고 마찬가지로 끝자리가 5가 되면 5로 나누어지기 때문에 0, 2, 4, 5, 6, 8가 뒤에 올수 없는 것이다.

 

 

📘풀이

1. 첫번째 숫자는 무조건 2, 3, 5, 7로 
2. 그 다음 숫자들은 1, 3, 7, 9 를 하나씩 넣어본 다음 만약 소수라면 return
3. 합친 숫자들이 소수이고 주어진 길이 n이라면 출력

 

마치 합체 시키듯이 뒤에 숫자들을 추가해준다. 소수라면 하나합체, 소수라면 하나합체 이렇게 n까지 반복하다가 n이 되면 출력해주는 것이다.

 

 

💻코드

def isprime(num): 
	# 소수 판별
    for i in range(2, int(int(num)**0.5)+1): 
        # 2~제곱근까지 쭉 나눠보고 나머지가 없다면 소수아님
        if int(num) % i == 0: 
            return 
    
    # 주어진 길이 n에 도달했다면 출력
    if len(num) == n:
        print(num) 
        return 

	# 다음 숫자인 1,3,7,9를 추가해준다.
    for j in secon: 
        isprime(num+j) 

n = int(input()) 
         
first = ['2', '3', '5', '7'] # 첫번째 숫자
secon = ['1', '3', '7', '9'] # 다음 숫자

for k in first: isprime(k)

 

📎문제링크: 신기한 소수

2023번: 신기한 소수