2023번

2023번 - 신기한 소수

처음에 에라토스테네스의 체를 이용해서 문제를 풀려고 했지만, 오히려 메모리 초과가 발생했다.

그래서 질문 게시판을 보고 힌트를 얻어서, 재귀함수를 통해서 정답을 구했다.

앞에서 부터 숫자를 채워가면서, 그 수가 소수인지 판별하는 함수를 만들어서 확인해줬다.

맨 앞 숫자는 0과 1이 들어가면 안된다는 점을 예외로 체크해줬다.

<정답 코드>

#include<iostream>
#include<vector>
#include<math.h>
#include<string>
using namespace std;
int n;
 
bool checkPrime(int num)
{
    for (int i = 2; i*i <= num; i++)
    {
        if (num%i == 0)
        {
            return false;
        }
    }
    return true;
}
void go(int len,string s)
{
    if (len == 0)
    {
        cout << s << "\n";
        return;
    }
 
    for (int i = 0; i <= 9; i++)
    {
        if ((i == 0 || i==1) && len == n)
        {
            continue;
        }
        string tmp = s;
        tmp += i + '0';
        int t = stoi(tmp);
 
        if (checkPrime(t))
        {
            go(len - 1, tmp);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;    
    string s = "";
    go(n,s);
    
 
    return 0;
}