C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 424K, 提交时间: 2022-12-06 20:02:28

#include<bits/stdc++.h>
using namespace std;
int n;
bool is_prime(int x){
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0){
			return 0;
		}
	}
	return 1;
} 
void dfs(int x,int k){
	if(!is_prime(x)){
		return;
	}
	if(k==n){
		cout<<x<<endl;
	}
	else{
		int d[4]={1,3,7,9};
		for(int i=0;i<4;i++){
			dfs(x*10+d[i],k+1);
		}
	}
}
int main(){
	cin>>n;
	dfs(2,1);
	dfs(3,1);
	dfs(5,1);
	dfs(7,1);
	return 0;
}

C++(clang++11) 解法, 执行用时: 6ms, 内存消耗: 380K, 提交时间: 2021-02-17 20:16:45

#include<bits/stdc++.h>
using namespace std;
int n;
bool is_prime(int x){
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0){
			return 0;
		}
	}
	return 1;
} 
void dfs(int x,int k){
	if(!is_prime(x)){
		return;
	}
	if(k==n){
		cout<<x<<endl;
	}
	else{
		int d[]={1,3,7,9};
		for(int i:d){
			dfs(x*10+i,k+1);
		}
	}
}
int main(){
	cin>>n;
	dfs(2,1);
	dfs(3,1);
	dfs(5,1);
	dfs(7,1);
}

Python3 解法, 执行用时: 51ms, 内存消耗: 4788K, 提交时间: 2023-01-06 15:20:33

n=int(input())
def prime(x):
    if x<2:return False
    for i in range(2,int(x**0.5)+1):
        if x%i==0:return False
    return True
def dfs(k,s):
    if not prime(s):return
    if k==n:
        if prime(s):print(s)
        return
    for i in [1,3,5,7,9]:
        dfs(k+1,s*10+i)
        
for i in [2,3,5,7]:
    dfs(1,i)