[백준] 2023번 : 신기한 소수

---

🔗 문제 링크

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

---

반응형

728x90

👩‍💻 코드

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

bool isPrime(int n) {
    for (int i = 2; i <= n/2; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

void DFS(int number, int place, int &N) {
    if (place == N) {
        if (isPrime(number)) {
            cout << number << "\n";
        }
        
        return;
    }

    for (int i = 1; i < 10; i++) {
        if (i % 2 != 0) {
            if (isPrime(number*10+i)) {
                DFS(number * 10 + i, place + 1, N);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    DFS(2, 1, N);
    DFS(3, 1, N);
    DFS(5, 1, N);
    DFS(7, 1, N);

    return 0;
}

---

📝 풀이

Do it! 알고리즘 코딩테스트 - C++ 편 : 기출 유형 분석부터 문제 풀이 비법까지!를 참고하였습니다.

 

한 자릿수 소수는 2,3,5,7이므로 탐색의 시작 수가 됩니다.

다음 자릿수부터는 홀수 1, 3, 5, 7, 9로 탐색을 이어갑니다.

일의 자리가 짝수인 경우는 소수가 아니므로 홀수로만 탐색을 합니다.

이러한 방식으로 자릿수가 N까지 도달했을 때 그 값이 소수라면 출력합니다.