백준 2023번 신기한 소수 - C++ 풀이

---

 

1. 길이 n짜리 신기한 소수의 집합을 P(n)이라고 하면 P(n) = (P(n-1)*10 + i) 중 소수인 것의 집합 (단, i는 0 ≤ i ≤ 9)

 

1. 길이 n짜리 신기한 소수의 집합을 P(n)이라고 하면 P(n) = (P(n-1)*10 + i) 중 소수인 것의 집합 (단, i는 0 ≤ i ≤ 9)

 길이 n짜리 신기한 소수 x가 있다고 하자. 그럼 x[0...(n-2)] 또한 신기한 소수이다. 따라서 재귀를 이용하여 구할 수 있다. 길이 n짜리 신기한 소수의 집합을 P(n)이라고 하면, P(n) = P(n-1)*10+i 중에서 소수인 것의 집합이 된다. 기저 사례는 n=1인 경우이고, 10 미만의 소수 {2, 3, 5, 7}을 리턴해주면 된다.

반응형

---

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

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

vector<int> calcInterestingPrimes(int len) {
    if (len == 1) return {2, 3, 5, 7};
    
    vector<int> ret;
    vector<int> arr = calcInterestingPrimes(len-1);
    
    for (auto x: arr) {
        for (int i=0; i<=9; i++) {
            if (checkPrime(x*10+i)) {
                ret.push_back(x*10+i);
            }
        }
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N;
    cin >> N;
    
    vector<int> ans = calcInterestingPrimes(N);
    for (auto x: ans) cout << x << "\n";
    
    return 0;
}