蓝桥杯算法提高VIP-特殊的质数肋骨 （C语言代码） DFS遍历， 有注释

解题思路:
符合该种质数的一位的质数为2， 3， 5， 7；而两位的质数为2x， 3x, 5x, 7x....

可以发现多一位位数即在前面是质数的基础上 * 10 再 加上 一个数，这个数很明显不能是偶数，因为除2外所有的偶数都不是质数。

所以我们就可以得到一个递推的式子： m = x * 10 + i，如果是质数则进入下一次：n = m * 10 + i；使用地推时需要注意的是出口，此时出口很明显是满足到要求的数字位数时即停止，同时输出该位数的数字，即可得结果。 


注意事项:
使用递推时要注意出口。

参考代码:

//1544: 质数肋骨 

#include <stdio.h>
#include <math.h>
int count = 0; 

//判断是否为质数 
int judge( int n )
{
	int i, j;
	
	for( i = 2 ; i <= sqrt(n) ; i ++ )
	{
		if( n % i == 0)
			return 0;
	}
	return n;
}

//判断是否达到要求的位数
//n 是第一位的数字，c 是位数 
int a10(int n, int c)
{
	int i, num;
	
//	在最后一次时，多执行了一次count--，所以选择将count+1或c-1 
	if( count == c - 1 )
	{
		printf("%d\n", n);
		return 0;
	}
	for( i = 1; i < 10 ; i++ )
	{
		num = n * 10 + i;
		if( judge(num) != 0 )
		{
			count ++;
			a10(num, c);
			count --;
		}
	}
}

int main()
{
	int n, i = 0, j, num = 1, end, ans[8], flag = 0, t;
	
	scanf("%d", &n);

//	1位数的质数2, 3, 5, 7.
//	所以输出必定以这4位数字开头，即最高位。
	
	 
	a10(2, n);
	a10(3, n);
	a10(5, n);
	a10(7, n);
	
	return 0;
	
}