USACO/sprime

分析

从数学的角度： 1.首位只能是质数2 3 5 7

2.其余位只能是1，3，7，9

3.若n=1，直接输出2，3，5 7

DFS

不需要预处理。 直接DFS 1～9，加入当前数末尾，并判断是不是素数，是则递归处理下一位数，不是则回溯，直到depth>n。不会超时。

---

用预处理…否则貌似会超时…先生成1位的质数,再用1位的质数生成2位,然后用2位的生成3位…就这样递归下去….最后一位直接全部输出然后Halt就好了… 下面代码是表示在原质数的基础的后面再加上一个奇数(因为质数除了2不可能是偶数)

tmp:=a[i-1,k]*10+b[l];

生成tmp之后再判断tmp是不是质数,易证循环只要到 根号tmp 过就好了

 for k:=2 to trunc(sqrt(i)) do    
 begin    
   if i mod k=0 then    
   begin    
     jump:=true;     
     break;     
   end;     
 end;  

如果是质数就把这个数记录到长度是这个数的长度的序号的数组里…

a[j,c]:=i;

这样预处理就不会超时了….最后只要把要求的长度的质数输出来就行了…

直接枚举法

预处理求出长度1~8所有符合条件的质数,方法很简单,而且效率极高. N=1的时候,只有2,3,5,7，N>1的时候,每一位只能是1,3,7,9.所以先求出N=1的素数,再用N=1的素数加上1,3,7,9，符合条件的数形成N=2的素数.再用N=2的用同样办法求出N=3的,以此类推.代码参考C++

动态规划法

设primes[i][*]保存位长为i的所有质数，size[i]表示位长为i的质数的个数。那么我们可以根据primes[i][*]的内容很快求出primes[i+1][*]的内容。

对所有的primes[i][j],因为个位上只可能是tail[4]={1,3,7，9}，对k=0 to 3,所以检查primes[i][j]*10+tail[k]是否是质数，若是，保存在primes[i][size[i]++]中；伪代码如下： for i 1 to n-1

  for j 0 to size[i-1]-1
      for k 0 to 3
          if(isPrime(primes[i-1][j]*10+tail[k])) 
              primes[i][size[i]++]=primes[i-1][j]*10+tail[k];

参考代码

/*
ID: wangbia1
PROG: sprime
LANG: C++
*/
#include<fstream>
#include<cmath>
#include<iostream>
 
using namespace std;
struct Element
{
	int pos;
	int shuju[4];
 
	Element()
	{
		pos = 0;
		shuju[0] = 1;
		shuju[1] = 3;
		shuju[2] = 7;
		shuju[3] = 9;
	}
};
bool isPrime(int i);//判断是不是质数
Element wei[8];//存储每一个位的信息,每一位占据一个空间
 
int main()
{
	ifstream fin("sprime.in");
	ofstream fout("sprime.out");
	int N;// 读取的几位数
	int which = 1;//表示在第几位
	unsigned value;
	int i = 0;
	unsigned temp = 1;
 
	fin >> N;
	wei[0].shuju[0] = 2;
	wei[0].shuju[1] = 3;
	wei[0].shuju[2] = 5;
	wei[0].shuju[3] = 7;
 
	for(int j = 0; j != N; ++j)
	{
		temp = temp * 10;//计算最大数值
	}
 
	value = wei[0].shuju[0];
	while(true)
	{
		if(wei[which].pos <= 3)
		{
			value = value * 10 + wei[which].shuju[wei[which].pos];//数据
			if(isPrime(value))//是质数
			{
				if(which != N - 1)//不是最后一位
				{
					which++;
				}
				else
				{
					if(value < temp)
						fout << value << endl;
					wei[which].pos++;
					value = value / 10;
				}
			}
			else//不是质数
			{
				wei[which].pos++;
				value = value / 10;
			}
		}
		else// 这个位已经到了最后一个数据了
		{
			wei[which].pos = 0;//下一轮重新开始
			which--;//前一位
 
			if(which < 0)//在最高位了
				break;
			value = value / 10;//数据还原
			wei[which].pos++;
		}
 
	}
 
	return 0;
}
 
bool isPrime(int i)
{
	bool tag = true;
	int place = (int)sqrt((double)i);
	int value;
	for(int j = 3; j <= place; j+=2)//质数判别
	{
		if(i % j == 0)
		{
			tag = false;
			break;
		}
	}
	return tag;
}

除了在计算以2为开始的时候有多余的判断，其他均没有多余的判断，个人感觉效率挺好，用时0.000s

当然了,如果怕超时,你可以打表.(那个面目狰狞的程序在c++里,自然一眼看出)

c
pascal
c++
Java

引用

[1]

[2]