boj 신기한 소수

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

소수란?
1과 자기 자신 이외의 약수가 없는 수
약수가 2개만 존재하는 수

요구사항 : n개의 수를 조합하여 소수를 만들고 조합하는 동안의 수도 모두 소수여야 한다.
ex)
n이 4일경우
2333은
2 는 소수이다.
23도 소수이다.
233도 소수이다.
2333도 소수이므로 출력

코드

#include <bits/stdc++.h>
using namespace std;

int n;
bool ok =false;

//a = 조합된 수  k=는 조합된 수의 갯수
void dfs(int a,int k){
    if(k==n){
    	// a가 짝수면 소수가 아니다.
       	if(a%2==0) return ;
        for(int i=3; i*i<=a; i+=2){
        	// 3부터 i*i이 a가 될때까지 나눠서 나머지가 0이 1번이라도 존재하면 소수가 아니므로 탈출
            if(a%i==0) return ;
        }
        //for문을 통과하면 소수라서 출력하고 탈출
        cout<<a<<"\n";
        return ;
    }
    for(int i=0; i<10; i++){
        a *=10;
        a+= i;
        if(a%2==0){
        //조합된 수가 2의 배수이면 다음 수로 넘어감
            a/=10;
            continue;
        }
        for(int j=3; j*j<=a; j+=2){
            if(a%j==0){
            	//조합된 수가 소수임을 판별
                ok=true;
                break;
            }
        }
        if(ok){
        	//조합된 수가 소수이므로 다음수로 넘어감
            ok=false;
            a/=10;
            continue;
        }
        dfs(a,k+1);
        // dfs를 돌고 나오면 a가 n자리 수 이므로 a를 /10하여 a를 n-1자리수로 변경
        a/=10;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    //시작은 모두 소수여야 한다. 한자리수에서 소수인경우 2,3,5,7
    dfs(2,1);
    dfs(3,1);
    dfs(5,1);
    dfs(7,1);

}