[BOJ]신기한 소수(2023)

난이도 - 골드5

분류 - DFS

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

예제 입력 1 복사

4

예제 출력 1 복사

2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393

 

풀이

 소수를 확인하는 법만 알고 있으면 간단한 문제이다. 소수를 확인하는 문제에서는 보통 아리스토테네스의 체가 더 많이 사용됐던것으로 기억하지만 여기서는 제곱근을 이용하여 수를 확인하며 DFS로 진행했다.

 

1. dfs함수에서 n은 숫자의 자리수이고 num은 소수인지 확인 할 수 이다.

 

2. 우선 n은 0~N-1을 자리수 범위로 본다( 0일때 한자리수 1일때 두자리수).  따라서 n == N일때는 num이 N자리 수이므로 checkPrime(소수판별기)의 반환값이 true이면 출력한다.

 

3. n이 N보다 작을 때에는 0~9까지 오른쪽에 추가(num*10+i)하며 소수인지 판별하고 소수에 대해서만 dfs 재귀를 돌린다.

 

※checkPrime은 num을 2~sqrt(num)(num의 제곱근)까지로 나누어 떨어질 때 소수가 아니므로 false, 나누어 떨어지지 않으면 true를 반환한다.

 이때 0과 1이 들어 온다면 모조건 true이므로(sq가 1이라서 while안으로 들어가지 않는다) if(num<2) 조건을 넣어준다.

코드

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int N;

bool checkPrime(int num) {
	if (num < 2)  return false;
	int sq = sqrt(num);
	while (sq>1) {
		if (num % sq == 0) return false; // 소수X
		sq--;
	}
	return true;	// 소수O
}
void dfs(int n, int num) {
	if (n == N) {
		if (checkPrime(num)) cout << num <<endl;
		return;
	}
	
	for (int i = 0; i < 10; i++) {
		int next = num * 10 + i;
		if(checkPrime(next)) dfs(n + 1, next);
	}
}
int main() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> N;

	dfs(0, 0);
	return 0;
}

 

※ 소수를 확인 하는 방법

 -제곱근 이용하기

 가장 쉬운 방법은 N이 소수인지 알아볼 때 2~N-1 까지 전부 나누는 것입니다. 하지만, 이렇게 하면 너무 시간이 오래 걸립니다.

 우리는 N의 제곱근보다 작은 수들을 나누어 보며 소수인지 판별할 수 있습니다.

 

bool checkPrime(int num) {
	if (num < 2)  return false;	// 1보다 작은 수는 while문 안으로 들어가지 않기 때문에 걸러줍니다.
	int sq = sqrt(num);			// num의 제곱근입니다. c++에서는 #include<cmath>가 필요한것 같습니다.
    							// cmath는 visual studio에서는 include를 안해줘도 실행 되지만
                                // 백준에서는 추가를 안하면 컴파일 에러가 뜨기 때문에 주의해야합니다.
	while (sq>1) {		//제곱근 ~ 2까지 확인하는 과정입니다.
		if (num % sq == 0) return false; // 소수가 아니면 false를 리턴합니다.
		sq--;
	}
	return true;	// 중간에 소수가 아니라면 false를 리턴했기 때문에 여기까지 왔다는 것은 소수라는 것입니다.
}

 

 -에라스토테네스의 체

 아리스토 테네스의 체는 범위가 N까지로 정해져 있을 때 모든 소수를 구할 때 유용한 방법입니다.

  원리는 x에 2~k(k는 x*k <= N이면서 가장 가까운 수)를 곱한 수는 모두 소수가 아니라는 점을 이용한 것입니다.

예를 들어서 2는 소수이죠? 그럼 2*2, 2*3, 2*4~~~ 은 소수가 아니므로 2*2부터 (2*n)까지 (N보다 작아야함) 모두 체크를 하는 식으로 구현합니다.

이후에는 3에 대해서 3*2, 3*3~~~ 그 후에는 4는 2*2로 체크 되었으니 5에 대해서 5*2~~~ 

이런식으로 원하는 범위를 구하면 되는 겁니다.

출력이 필요하다면 2, 3, 5  즉, 체크를 시작하는 수에서 출력을 하거나 마지막에 체크가 안되어 있는 수에 대해서 출력하면 되겠죠?

 

간단한 코드를 보시겠습니다.

// N보다 작은 소수를 출력하겠습니다.
vector<bool> arr;
	for (int i = 2; i <= N; i++) {
		if (arr[i]) continue;	// arr[i]가 체크되어 있으면 소수가 아니므로 넘어갑니다.
        cout << arr[i]; // 예를 들면 2, 3, 5와 같은 소수에서 출력을 진행합니다.
		for (int j = i; j <= K; j+=i) {	// 소수의 배수들 (ex.2*2,3*2...)은 소수가 아니므로
			arr[j] = true;				// 체크해줍니다.
		}
	}