PS Featured

[PS] BOJ 2023 / 신기한 소수

Minjun Kim

29 Dec 2025 • 2 min read

Thumbnail: Photo by James Orr (Unsplash)

문제 링크: https://www.acmicpc.net/problem/2023

풀이

신기한 소수?

길이가 $N$인 수 중 신기한 소수란, 왼쪽부터 1자리, 2자리, $\cdots$, $N$자리의 숫자가 모두 소수인 수를 말합니다.

우리는 $N$자리의 모든 신기한 소수를 사전 순으로 찾아 출력해야 합니다. 먼저, $N$자리의 신기한 소수를 만드는 방법부터 생각해봅시다.

$N$자리의 신기한 소수 만들기

먼저, 왼쪽부터 첫 자리는 소수여야 하므로 알려진 한 자리 소수인 2, 3, 5, 7 중에서 하나를 골라 수를 구성합니다.

이후 과정에서는 0~9까지의 수를 하나씩 사용해 보며, 현재까지 만들어진 수가 소수인지 확인해 소수인 경우에만 다음 자릿수를 찾는 과정을 반복합니다. 이는 백트래킹을 통해 구현할 수 있습니다.

def build(number, index):
    if index == N:
        print(number)
        return
    
    for d in range(10):
        new_number = number * 10 + d
        if is_prime(new_number):
            build(new_number, index + 1)

# 왼쪽에서 첫 자리의 숫자는 무조건 한 자리 소수여야 한다.
for i in (2, 3, 5, 7):
    build(i, 1)

백트래킹으로 길이가 N인 신기한 소수 만들기

이 때, 결과를 사전순으로 출력하기 위해서는 항상 작은 수 부터 큰 수 순으로 수를 만들면 됩니다.

소수 빠르게 판별하기

백트래킹 과정에서, 지속적으로 현재 수가 소수인지 판별해야 합니다. 이를 위해, 어떤 수가 소수인지 판별하는 함수 is_prime(n)을 정의해 봅시다.

from math import sqrt

def is_prime(number):
    for i in range(2, int(sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True

소수 판별 함수

어떤 수 $N$이 소수인지 판단하기 위해서는, 2부터 $\sqrt{N}$까지의 수로 $N$을 나누었을 때 나누어 떨어지는 경우가 있는지 찾으면 됩니다.

전체 코드

from math import sqrt
input = open(0).readline
N = int(input())

def is_prime(number):
    for i in range(2, int(sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True

def build(number, index):
    if index == N:
        print(number)
        return
    
    for d in range(10):
        new_number = number * 10 + d
        if is_prime(new_number):
            build(new_number, index + 1)

# 왼쪽에서 첫 자리의 숫자는 무조건 한 자리 소수여야 한다.
for i in (2, 3, 5, 7):
    build(i, 1)

solution.py