【DFS深度优先搜索】【欧拉筛法】【洛谷P5540】

传送门

 
#include
using namespace std;
int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
string str;
const int maxn=100000010;
bool nums[maxn];
long long f[10000001],cot=0;
int ans=0;
//每一次进行判断    O(nlongn)  爆点  得优化 
bool prime(int n)
{
	if(n==1) return false;//！！！1它不是素数 
	for(int i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)
			return false;
	}
	return true;
}
bool check(int sum)//检查是否合格 
{
	int year=sum/10000;
	int month=sum/100%100;
	int day=sum%100;
	if(year%400==0||(year%4==0&&year%100!=0))
		months[2]=29;
	else
		months[2]=28; 
	return year>=1&&year<=9999&&month>=1&&month<=12&&day>=1&&day<=months[month];
}
void dfs(int layer,int sum)//O(2e7) 
{
	int num;
	if(layer==8)
	{
		if(check(sum)&&!nums[sum%10000]&&!nums[sum%100]&&!nums[sum])
		{
			ans++;
		}
	}
	else if(str[layer]!='-')
	{
		num=(str[layer]-'0')*pow(10,7-layer);
		dfs(layer+1,num+sum);
	}
	else
	{
		if(layer==4)//优化 月的十位数   
		{
			for(int i=0;i<=1;i++)
			{
				num=i*pow(10,7-layer);
				dfs(layer+1,num+sum);
			}
		}
		else
		{
			for(int i=0;i<=9;i++)
			{
				num=i*pow(10,7-layer);
				dfs(layer+1,num+sum);
			}
		}
	}
}
int main()
{
	 
	nums[1]=true;//1不是素数 
	long long n=1e8;
    for(long long i=2;i<=n;i++)
    {
        if(!nums[i])
            f[cot++]=i;
        for(long long j=0;j>t;
	while(t--)
	{
		cin>>str;
		ans=0;
		dfs(0,0);
		cout<