深搜

#include <bits/stdc++.h>

#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)

using namespace std;

bool is_prime (int x) // 判断是否是素数
{
    if (x <= 1)
        return false;
    if (x == 2 || x == 3)
        return true;
    if (x % 6 != 1 && x % 6 != 5)
        return false;
    for (int i = 5; i * i <= x; i += 6)
        if (x % i == 0 || x % (i + 2) == 0)
            return false;
    return true;
}

int n;

void dfs (int x, int sum)
{
    if (x == n + 1)
    {
        printf ("%d\n", sum);
        return;
    }
    for (int i = 1; i <= 9; i++)
    {
        if (is_prime (sum * 10 + i))
            dfs (x + 1, sum * 10 + i);
    }
}

int main ()
{
    scanf ("%d", &n);
    dfs (1, 0);// 从1位数开始搜索
    return 0;
}