[백준] 2023-신기한 소수(C++)

문제링크:www.acmicpc.net/problem/2023

2023번: 신기한 소수

 

에라토스 체 알고리즘을 사용하면 n=8일때 시간초과가 일어납니다.

오히려 체알고리즘을 사용하지 않고 문제 조건 처럼  왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수인지

순서대로 찾아주는 것이 효율적입니다.

 

이를 재귀함수를 통해서 구현했습니다.

 

• 1. 첫수를 항상 2,3,5,7로 시작한다.
• 2. 그 이후 숫자는 반복문을 통해서 소수인지 확인하며 진행한다. 
• 3. 재귀함수가 n번 탐색했다면 해당 수는 소수이므로 바로 출력한다.

 

 

아래는 정답 코드입니다.

#include <iostream>
using namespace std;

int n = 0;

bool checked(int num) {

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

void dfs(int num, int len) {
	if (len == n) {
		cout << num << "\n";
		return;
	}

	for (int i = 1; i <= 9; i++) {
		if (checked(num * 10 + i))
			dfs(num * 10 + i, len + 1);
	}

	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	

	
	cin >> n;
	dfs(2, 1);
	dfs(3, 1);
	dfs(5, 1);
	dfs(7, 1);
	return 0;
}