2023번

2023

#include <iostream>
#include <string>
#include <math.h>

using namespace std;

int n;
string primeNum[4] = {"2", "3", "5", "7"};

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

void dfs(string numStr) {
	if(numStr.length()==n) {
		cout<<numStr<<endl;
		return;
	}

	for(int i=1; i<=9; i++) {
		if(i%2 ==0) continue;
		string newNumStr = numStr + to_string(i);
		if(isPrime(newNumStr)) {
			dfs(newNumStr);
		}
	}
}

int main() {
	cin >> n;
	string numStr = "";
	
	for(int i=0; i<4; i++) {
		numStr = primeNum[i];
		
		if(n!=1) {
			dfs(numStr);
		}
	}
	
	if(n == 1) {
		for(int i=0; i<4; i++) {
			cout<<primeNum[i]<<endl;
		}
	}
	
}