[solved.ac 골드5] 2023_신기한 소수 (파이썬, BFS)

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

문제

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

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

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

입력

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

출력

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

예제

 

---

나의 풀이

이 문제의 키 포인트는 다음과 같다고 생각한다.

• 어떤 수 n의 소수 판별
• 신기한 소수 만들기

 

소수 판별

소수를 판별하는 가장 쉬운 방법은 확인하고자 하는 수가 n이라고 했을 때 n보다 작은 수로 나눠보는 것이다.

하나라도 나누어 떨어지는 수가 있으면 소수가 아닌 것이고, 나누어 떨어지는 수가 없다면 소수인 것이다.

하지만 n보다 작은 모든 수로 나누게 되면 O(n) 만큼의 시간 복잡도가 소요되어 시간이 많이 소요될 것이다.

결론부터 말하자면 n의 제곱근 까지만 나눠보면 된다.

예를 들어 10이라는 숫자를 판별하려고 한다면 다음과 같이 나눠볼 수 있다.

• 1 x 10 = 10
• 2 x 5 = 10
• 5 x 2 = 10
• 10 x 1 = 10

나누어 떨어지는 수를 확인해보면 1, 2, 5, 10으로 나눴을 때 나누어 떨어진다.

나누어 떨어진다는 것은 어떤 두 수의 곱으로 표현할 수 있다는 것인데, (a, b) 라는 두 수의 곱으로 나타낼 수 있다면 (b, a) 로도 나타낼 수 있다. 위 예시에서 (1, 10) = (10, 1), (2, 5) = (5, 2) 인 것과 같다. (곱의 교환 법칙 성립)

그렇다면 10이나 5로 굳이 나눠보지 않아도 1과 2로 나눠보면 나누어 떨어지는 것을 이미 알 수 있다. 즉, 두 수가 있을 때 더 작은 수로 나눠보면 끝까지 나눠보지 않아도 된다는 것이다.

그렇다면 여러 개의 숫자 쌍이 있을 때 더 작은 수 중에서 가장 큰 수는 무엇일까? 그게 바로 제곱근이다.

정리하자면 2부터 제곱근까지 차례대로 나누는 동안 한 번이라도 나누어 떨어지면 그 수는 합성수(소수가 아님)라는 것이다.

2부터 나누는 이유는 소수의 정의가 1과 자기 자신으로만 나누어 떨어지는 수이기 때문에 1이 아닌 2부터 나눠본다. 단, 이 경우에 예외가 있다. 바로 2이다. 2는 유일하게 2로 나눠지는 소수이다.

def is_prime(n):
    for i in range(3, int(n ** (1 / 2)) + 1): # 3 ~ root(n)까지 나눠보기
        if not n % i: return False # 나누어 떨어지면 합성수
    return True # 나누어 떨어지는 수가 없으면 소수

코드를 보면 2가 아닌 3부터 나눠보기 시작했다. 위에서 말했듯이 2는 위 식에서는 소수가 아닌 것으로 판별되기 때문에 2를 예외로 두기 위해서 3부터 나눠보기 시작했고, 단!! is_prime으로 들어오는 n은 홀수만 들어오도록 했다.

 

신기한 소수 만들기

예를 들어 2333 이라는 수를 찾기 위해서는 233도 소수여야 하고, 23도 소수여야 하고, 2도 소수여야 한다.

만약 어떤 소수 23을 찾았다고 했을 때 23 뒤에 어떤 숫자를 붙였을 때 그 수가 소수가 되면 또 그 수를 가지고 4자리 소수를 찾으면 된다. 3을 붙여서 233이 소수가 되었을 때 233 뒤에 어떤 숫자를 붙이면 소수가 되는지를 찾으면 되는 것이다.

2, 23, 233, 2333을 순차적으로 찾을 수 있기 때문에 큐를 사용하는 BFS를 사용해서 찾아나갈 수 있다.

큐에는 소수만이 입력될 수 있고, 큐에서 빼낸 어떤 수 n 뒤에 다른 숫자를 붙여서 그 수가 또 다시 소수가 된다면 큐에 넣는다.

만약 큐에서 나온 수가 찾고자 하는 자릿수라면 출력만 하고 더 이상 그 수로는 소수를 찾지 않는다. (큐에 넣지 않는다)

from collections import deque


def is_prime(n):
    for i in range(3, int(n ** (1 / 2)) + 1): # 3 ~ root(n)까지 나눠보기
        if not n % i: return False # 나누어 떨어지면 합성수
    return True # 나누어 떨어지는 수가 없으면 소수


def bfs():
    q = deque([2, 3, 5, 7]) # 한 자리 수 소수들
    while q:
        n = q.popleft()
        if n // (10 ** (limit - 1)) > 0: # 숫자 길이가 limit인지 확인
            print(n) # 출력
        else:
            for i in range(1, 10, 2): # 1, 3, 5, 7, 9
                if is_prime(n * 10 + i): # 뒤에 숫자 붙이고(홀수만) 소수 판별
                    q.append(n * 10 + i) # 큐에 넣기

limit = int(input())
bfs()

 

채점 결과