[백준 골드5] 2023 신기한 소수

https://www.acmicpc.net/problem/2023

 

자릿수가 한 개인 소수 2,3,5,7을 시작으로 탐색한다. 

이어서 자릿수가 두 개인 현재 수 * 10 + a를 계산하여 이 수가 소수인지 판단하고,

소수라면 재귀 함수로 자릿수를 하나 또 늘린다.

단 a가 짝수인 경우 항상 2를 약수로 가지므로 가지치기로 a가 짝수인 경우를 제외한다.

이런 방식으로 자릿수를 N까지 확장했을 때 그 값이 소수라면 해당 값을 출력한다.

 

이러한 방식으로 DFS를 이용한 탐색이 가능하다.

 

#include <string>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <deque>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <set>


using namespace std;

int N;

void DFS(int num, int j);
bool isPrime(int num);



int main()
{
    ios::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 num, int j)
{
    if (j == 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)) {
            DFS(num * 10 + i, j + 1);
        }
    }
}

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