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

#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 recurse(int first, int n) {
    if (n == 0) {
        cout << first << "\n";
        return;
    }

    for (int i = 1; i < 10; i += 2) {
        int tmp = first * 10 + i;
        if (isPrime(tmp))
            recurse(tmp, n - 1);
    }
}

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

    int n; cin >> n;
    int first[4] = { 2, 3, 5, 7 };

    for (int i = 0; i < 4; i++)
        recurse(first[i], n - 1);

    return 0;
}

 

1. 첫 번째 자리는 2, 3, 5, 7만 와야하므로 first 배열 생성

2. 재귀 함수와 소수 판별 함수 사용

3. 예를 들어 21이 소수로 판별되면 recurse(재귀 함수)에 21을 다시 넣고, 210 + 1 ~ 210 + 9에 대한 소수 판별을 진행

=> 소수 판별을 진행하던 중 소수가 발견되면 다시 재귀 함수에 해당 소수를 넣음

4. 만약 n이 0이면 해당 소수 출력 후 재귀 함수 종료

 

 

최하단 for문의 i 범위를 잘못 잡아 틀린 문제