2023번 (gold 5)

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

간단하게 재귀함수로 풀 수 있는 문제이다.

 

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

void DFS(int, int, int);
bool isPrime(int);
static vector<int> arr;
int main() {
	cin.tie(0)->sync_with_stdio(false);
	int N;
	cin >> N;

	DFS(2, N, 1);
	DFS(3, N, 1);
	DFS(5, N, 1);
	DFS(7, N, 1);
	for (auto& it : arr) {
		cout << it << '\n';
	}
	return 0;
}

void DFS(int num, int digit, int n) {
	if (isPrime(num)) {
		if (digit == n) {
			arr.emplace_back(num);
			return;
		}
		else{
			for (int i = 1; i <= 9; ++i) {
				DFS(num * 10 + i, digit, n + 1);
			}
		}
	}
}

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

	is_prime = true;

	return is_prime;
}