[백준] 2023 - 신기한 소수

문제

• 링크: https://www.acmicpc.net/problem/2023
• 난이도: Gold IV
• 태그: 수학, 정수론, 백트래킹, 소수 판정

풀이

#include <bits/stdc++.h>

using namespace std;

int n;

bool isPrime(int num)
{
	for (int i = 2; i <= num / 2; ++i)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

void solve(int num, int digit)
{
	if (digit == n)
	{
		if (isPrime(num))
		{
			cout << num << "\n";
		}

		return;
	}

	for (int i = 1; i < 10; i++)
	{
		if (i % 2 == 0)
		{
			continue;
		}

		if (isPrime(num * 10 + i))
		{
			solve(num * 10 + i, digit + 1);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	solve(2, 1);
	solve(3, 1);
	solve(5, 1);
	solve(7, 1);

	return 0;
}

백트래킹으로 하나하나 시도하면 된다. 일단 한 자릿수 소수는 2, 3, 5, 7이므로 이 숫자로 탐색을 시작한다. 그 뒤에 붙는 수들은 일의 자리가 되므로 홀수로만 붙여나가면 된다(2를 제외한 모든 소수는 홀수이므로).

배운 점과 후기

소수의 정의에 따라 후보군을 좁혀나간다는 점에서 백트래킹의 개념을 리마인드하기 좋은 문제인 것 같다.