[BOJ/C++] 2023 신기한 소수

N자리의 숫자를 왼쪽에서부터 1자리~N자리의 모든 숫자가 소수인 숫자를 찾는 문제입니다.

각 자리의 숫자에 대해 DFS를 이용하여 문제를 해결할 수 있습니다.

예를 들어 숫자가 2333이라면 2, 23, 233, 2333 모두 소수이므로 신기한 소수가 됩니다.

1자리 숫자중 소수는 2, 3, 5, 7 이므로 이 숫자를 시작으로 DFS를 시작하면 됩니다.

이후 홀수인 1, 3, 5, 7, 9에 대해 해당 자리수까지 탐색하면 됩니다.

해당 자리수까지 모두 소수인 숫자를 출력하면 됩니다.

// boj g5 2023
// 신기한 소수

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

static vector<int> G = { 1,3,5,7,9 };
//static vector<bool> visited;

void DFS(int v, int n);
bool isPrime(int n);
static int N;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	DFS(2, 1);
	DFS(3, 1);
	DFS(5, 1);
	DFS(7, 1);

	return 0;
}

void DFS(int v, int n)
{
	if(n==N)
	{
		if(isPrime(v))
		{
			cout << v << '\n';
		}
		return;
	}
	for(int i : G)
	{
		if (isPrime(v * 10 + i))
			DFS(v * 10 + i, n + 1);
	}
}

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