博客

49 我素故我在

作者: xxx时间限制: 1S章节: 深度优先搜索

问题描述 :

有这样一种素数叫纯素数(YY出来的名字)，当它是一个多位数的时候，你把它的末位去掉之后余下的数依然是一个素数。比如说2393，2393 本身是一个素数，它的末位去掉之后，余下的是239。239 是一个素数，它的末位去掉之后，余下的是23 。23是一个素数，它的末位去掉之后，余下的是2 。2依然还是一个素数。纯素数的长度叫做“维”。2393 是一个4维素数。3797也是一个4维素数。

输入说明 :

第一行先给出一共有多少组数据N(N<=1000),接下来有N组数据.

每组包括一个整数T(1<=T<=8)。

输出说明 :

按照从小到大的顺序输出所有的T维纯素数。

输入范例 :

3
8
1
4

输出范例 :

23399339
29399999
37337999
59393339
73939133
2
3
5
7
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

解答思路：

这题暴力是肯定超时的，按提示的dfs来就是了。打表把所有纯素数找出来。

二维数组。一维质素有2357 二维只要搜索一维质素每个尾部添加1-9是不是质数就行了。

AC代码

#include <stdio.h>
#include <math.h>

int iszhi(int n)
{
	if(n==0||n==1)
	{
		return 0;
	}
	for(int p=2;p<n;p++)
	{
		if(n%p==0)
		{
			return 0;
		}
	}
	return 1;
}


void set(int a[][1000],int i,int len)  		//i代表维度 也是二维度数组中的下标。i=0时存一维纯质数。
{
	if(i==8)
	{
		return;
	}
	if(i==0)					//因为要搜索i-1层，所以当i=0时单独算 也可以从1开始存储 那样就不需要区分了
	{
		for(int j=1;j<=9;j++)
		{
			if(iszhi(j))
			{
				a[i][len++]=j;

			}
		}
		set(a,i+1,len);			//一维弄完弄二维，len是一维质数的个数。
	}
	else
	{
		int templen=0;
		for(int v=0;v<len;v++)
		{
			for(int u=1;u<=9;u++)
			{
				int tempnum=10*a[i-1][v]+u;
				if(iszhi(tempnum))
				{
					a[i][templen++]=tempnum;
				
				}
			}
		}
		set(a,i+1,templen);
	}

}



int main()
{
	int t;
	scanf("%d",&t);

	int a[8][1000]={0};
	int i=0,len=0;
	set(a,i,len);

	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int r=0;;r++)
		{
			if(a[n-1][r]==0)			//没有开一个存储长度的数组，用初始化的0判断结束。
			{
				break;
			}
			printf("%d\n",a[n-1][r]);
		}
	
	
	}


}