BaekJoon(2023)::신기한 소수

문제

2023번: 신기한 소수

문제파악

해당 문제는 N자리의 수가 주어질 경우 해당 수의 왼쪽부터 1자리,2자리 3자리가 전부 소수인 소수를 구하는 문제가 된다. 

즉, 해당 문제를 푸는데 있어서 내가 든 생각은 다음 조건들이 있다는 생각이 들었다.

1. 각 자리의 수 : 0~9
2. 소수 판별
3. N자리 수만큼 반복

이러한 조건들을 생각해보고 문제를 해결해 보았다.

문제풀이

#include<iostream>

using namespace std;

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


void get_prime(int prime, int n) {
	if (n == 0) {
		cout << prime << endl;
	}

	for (int i = 1; i <= 9; i++) {
		int temp = prime * 10 + i;
		if (isPrime(temp)) {
			get_prime(temp, n - 1);
		}

	}

}

int main() {
	int n;
	int single_prime[4] = { 2, 3, 5, 7 };

	cin >> n;

	for (int i = 0; i < 4; i++) {
		get_prime(single_prime[i], n - 1);
	}

	return 0;
}