USACO-T020: Super Prime Rib

/*
ID: mickyta1
TASK: sprime
LANG: C++
*/

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

vector<int> ans;
int n;

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

void recur(int d, int x){
    if(d > n){
        ans.push_back(x);
        return;
    }
    for(int i = 0; i <= 9; ++i){
        int newX = 10 * x + i;
        if(isPrime(newX)){
            recur(d + 1, newX);
        }
    }
}

int main(){
    freopen("sprime.in", "r", stdin);
    freopen("sprime.out", "w", stdout);

    scanf("%d", &n);
    recur(1, 0);
    sort(ans.begin(), ans.end());
    for(int x : ans){
        cout << x << '\n';
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}