pprime.cpp

USACO Section 1-4的后两个程序以及Section 1-5的全部程序代码

/*
NAME:lemon_c1
LANG:C++
PROG:pprime
*/
#include<fstream>
#include<cmath>
using namespace std;
ifstream cin("pprime.in");
ofstream cout("pprime.out");
const int pows[9]={1,10,100,1000,10000,100000,1000000,10000000,100000000};
int n,m;
int cnum;
int upper;
int downer;
void dfs(int layer);
bool isprime(int s)
{
	int t=(int)(sqrt(s));
	for(int i=2;i<=t;i++)
		if(s%i==0)return false;
	return true;
}
int main(void)
{
	cin>>n>>m;
	int t=(int)(log(m)/log(10)+1);
	downer=(int)(log(n)/log(10)+1);
	for(upper=downer-1;upper<t;upper++)
		dfs(0);
	return 0;
}
void dfs(int layer)
{
	if(layer==upper/2)
	{
		for(int i=0;i<=9;i++)
		{
			cnum+=pows[layer]*i;
			if(upper%2)cnum+=pows[layer+1]*i;
			if(cnum>m)return;
			if(cnum<n)
			{
				cnum-=pows[layer]*i;
				if(upper%2)cnum-=pows[layer+1]*i;
				continue;
			}
			if(isprime(cnum))
				cout<<cnum<<endl;
			cnum-=pows[layer]*i;
			if(upper%2)cnum-=pows[layer+1]*i;
		}
		return;
	}
	if(layer==0)
	{
		for(int i=1;i<=9;i+=2)
		{
			cnum+=i;
			cnum+=i*pows[upper];
			if(cnum>m)return;
			dfs(layer+1);
			cnum-=i*pows[upper];
			cnum-=i;
		}
		return;
	}
	for(int i=0;i<=9;i++)
	{
		cnum+=pows[layer]*i;
		cnum+=pows[upper-layer]*i;
		if(cnum>m)return;
		dfs(layer+1);
		cnum-=pows[upper-layer]*i;
		cnum-=pows[layer]*i;
	}
}