蓝桥杯算法提高-特殊的质数肋骨 （小小地尝试一下递归）

这个题目的关键是我们要注意 N位数的最高位可以为1-9

其他的位数只能为1，3，5，7  .

之后再采用递归的方法 找出每个位数的四种情况 加上最高位的9种情况

一一进行特殊素数的判定  

给大家一个小提示  递归可以代替循环次数是个变量的for循环

写的有点乱了  思路也不怎么清晰  欢迎大家指正批评！

#include<iostream>
#include<algorithm>
using namespace std;
int a[10];
int s;//用来保存N
int k=0;
int b[1000];//保存特殊质数 之后进行排序输出
bool prime(int n)//素数判定
{
	if(n<2)
	return false;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
		return false;
	}
	return true;
}
void f(int n)
{
	//cout<<"n="<<n<<endl;
	if(n==1)//直到n==1 意味着是最高位
	{
	  for(int i=1;i<=9;i++)//最高位有9种情况
	  {
	  	a[n]=i;//对最高位的每种情况 计算所得数是不是特殊质数
	  	int sum=0,flag=0;
	  	for(int j=1;j<=s;j++)
	  	{
	  	sum=sum*10+a[j];//依次判断数字种减除每一位后是否还是质数
	  	if(!prime(sum))
	  	 {
	  	 	flag=1;
	  	 	break;
		 }
	  	}
	  	if(flag==0)
	  	b[k++]=sum;//将这些特殊质数放入b数组
	  }
	  return;	
	}
	else
	{
		for(int i=1;i<=9;i+=2)
		{
			a[n]=i;//第n位数有1，3，5，7四种情况
			f(n-1);//接着讨论第n-1位数的四种情况.
		}
	}
}
int main()
{
	int N;//特殊质数的位数
	while(cin>>N)
	{
	  s=N;//s为全局变量
	  f(N);		
	  sort(b,b+k);//进行排序后输出
	  for(int i=0;i<k;i++)
	  {
	  	cout<<b[i]<<endl;
	  }
	}
	return 0;
 }