蓝桥杯算法提高VIP-特殊的质数肋骨 （C++代码）

解题思路:





注意事项:





参考代码:

深搜（dfs）:

#include<bits/stdc++.h>//万能头文件
using namespace std; 
int n1[4]={2,3,5,7};//质数肋骨的首位数字可能性 
int n2[4]={1,3,7,9};//质数肋骨后几位的数字可能性 
int n;//位数 
bool is_prime(int x) //素数判断 { 
    for(int i=2;i*i<=x;i++) 
    if(x%i==0) 
    return false; 
    return true; 
} 
void dfs(int s,int i)//深搜函数 { 
    int ss; 
    if(i==n)
    {        
    cout<<s<<endl;        
    return;
    }//如果i==n,输出当前的s 
    for(int j=0;j<4;j++)
    {//循环拼数 
        ss=s*10+n2[j];//当前s*10+后几位的可能数字 
        if(is_prime(ss)) 
        dfs(ss,i+1);//如果ss为素数，则继续往下深搜 
    } 
} 
int main()//主函数开始 { 
    //freopen("superprime.in","r",stdin); 
    //freopen("superprime.out","w",stdout); 
    cin>>n;//读入n 
    if (n==1)
        cout<<2<<endl<<3<<endl<<5<<endl<<7;//直接输出1的情况 
    else 
    { 
        for(int i=0;i<4;i++)//循环深搜 
        dfs(n1[i],1); 
    } 
    return 0;
}