2023 신기한 소수

#include <iostream>

using namespace std;

int N;

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

    return true;
}

void dfs(int number, int digit)
{
    if (digit == N) {
        cout << number << endl;
    }
    for (int i = 1; i < 10; i += 2) {
        if (isPrimeNumber(number * 10 + i)) {
            dfs(number * 10 + i, digit + 1);
        }
    }
}

void solve()
{
    int start[4] = {2, 3, 5, 7};
    for (int i = 0; i < 4; i++) {
        dfs(start[i], 1);
    }
}

void input()
{
    cin >> N;
}


int main(void)
{
    input();
    solve();

    return 0;
}

dfs로 높은 자릿수부터 하나씩 감소하면서 탐색했다.

소수는 에라토스테네스의 체를 이용해서 판별했다.

자꾸 시간초과가 떠서 고생했는데 첫번째 자리부터 소수여야 한다는 조건을 이용했다.

첫번째 자리의 수를 2, 3, 5, 7로 한정시키니 시간초과 문제를 해결할 수 있었다.