[BOJ 2023] 신비한 소수

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

갓 갈자님이 추천해서 풀었다가 열심히 삽질했다. 느낀점은 소수 구할때 그냥 에라토스체 안돌리고 그냥 sqrt(n)까지의 범위에서 나눠지는게 있는지 아닌지만 판별하면 그 숫자가 소수인지 아닌지 판별 가능하다는 점이다. 

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

이렇게 이렇게 ..

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define INF 1000000000
typedef long long ll;
 
using namespace std;
 
bool chk (int x){
    for(int i=2;i<=sqrt(x);i++){
        if(x%i == 0){
            return false;
        }
    }
    return true;
}
 
void solve(int num,int pos){
    if(pos == n){
        cout << num<< endl;
        return;
    }
    if(chk(num*10+1) && num>1){
        solve(num*10+1,pos+1);
    }
    if(chk(num*10+2)){
        solve(num*10+2,pos+1);
    }
    if(chk(num*10+3)){
        solve(num*10+3,pos+1);
    }
    if(chk(num*10+5)){
        solve(num*10+5,pos+1);
    }
    if(chk(num*10+7)){
        solve(num*10+7,pos+1);
    }
    if(chk(num*10+9)){
        solve(num*10+9,pos+1);
    }
}
 
 
int main(){
    
    
    cin >>n;
    solve(0,0);
    
    
    
    return 0;
}