[USACO] 1-5-3 Superprime Rib

/*
ID: 551100k1
LANG: C++
TASK: sprime
*/
#include<stdio.h>
int s[1000005]={0},prime[100005]={0},top=0,n;
bool check(long long int k){
    if(k==1) return 0;
    long long int i;
    for(i=0;prime[i]*prime[i]<=k;i++)
        if(k%prime[i]==0) return 0;
    return 1;
}
void dfs(int k,int v){
    if(check(k)==0) return;
    if(v==n){
        printf("%d\n",k);
        return;
    }
    int i;
    for(i=1;i<=9;i++)
        dfs(k*10+i,v+1);
}
int main(){
    freopen("sprime.in","r",stdin);
    freopen("sprime.out","w",stdout);
    int i,j;
    s[1]=1;
    for(i=2;i<=1000000;i++){
        if(s[i]==0){
            for(j=i+i;j<=1000000;j+=i)
                s[j]=1;
            prime[top++]=i;
        }
    }
    scanf("%d",&n);
    dfs(0,0);
}