#include<bits/stdc++.h>
using namespace std;
int n,m;
bool isPrime(int a){
	if(a<2) return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0) return false;
	}
	return true;
}
void dfs(int a,int length,int n){
	if(length==n){
		cout<<a<<endl;
		return;
	}
	for(int i=1;i<=9;i++){
		int b=a*10+i;
		if(isPrime(b)){
			dfs(b,length+1,n);
		}
	}
}
int main(){
	cin>>n;
	int first[]={2,3,5,7};
	for(int i=0;i<4;i++){
		dfs(first[i],1,n);
	}
	return 0;
}

广告：程序设计中的数学

打表

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
int n;

bool isp(int n) {
    for (int i = 2; i <= n / i; i++)
        if (n % i == 0)
            return 0;
    return n > 1;
}
void PD() {
    vector<int> ans[N];
    int r = pow(10, 8) - 1;
    for (int i = 2; i <= r; i++) {  // i=123
        int t = i, cnt = 0;
        while (isp(t))
            t /= 10, cnt++;
        if (t == 0)
            ans[cnt].push_back(i);
    }
    for (int i = 1; i <= 8; i++) {
        for (auto u : ans[i])
            cout << u << ",";
        cout << "-------------" << endl;
    }
}
vector<int> ans[10] = {
// 按要求对素数（1~8位）打表
{},
{2,3,5,7},
{23,29,31,37,53,59,71,73,79},
{233,239,293,311,313,317,373,379,593,599,719,733,739,797},
{2333,2339,2393,2399,2939,3119,3137,3733,3739,3793,3797,5939,7193,7331,7333,7393},
{23333,23339,23399,23993,29399,31193,31379,37337,37339,37397,59393,59399,71933,73331,73939},
{233993,239933,293999,373379,373393,593933,593993,719333,739391,739393,739397,739399},
{2339933,2399333,2939999,3733799,5939333,7393913,7393931,7393933},
{23399339,29399999,37337999,59393339,73939133}};
    
int main() {  // PD();
    cin >> n;
    for (auto u : ans[n])
        cout << u << endl;
}

筛法

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e8 + 10, INF = 0x3f3f3f3f;
int n, pri[N], pn;
bool st[N];

void es(int mx) {
    st[0] = st[1] = 1;
    for (int i = 2; i <= mx; i++) {
        if (!st[i]) pri[++pn] = i;
        for (int j = 1; j <= pn && pri[j] <= mx / i; j++) {
            st[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
        }
    }
}
int main() {
    es(1e8); cin >> n;
    int l = pow(10, n - 1), r = pow(10, n) - 1;
    for (int i = l; i <= r; i++) {
        int t = i, f = 1;
        while (t) {
            if (st[t]) { f = 0; break; }
            t /= 10;
        }
        if (f) cout << i << endl;
    }
    return 0;
}