sprime.cpp

来自「USACO Section 1-4的后两个程序以及Section 1-5的全部程」· C++ 代码 · 共 50 行

/*
NAME:lemon_c1
LANG:C++
PROG:sprime
*/
#include<iostream>
#include<cctype>
#include<cmath>
using namespace std;
const char p1[4]={'2','3','5','7'};
const char p2[6]="13579";
char s[9];
int n;
void dfs(int d);
int main(void)
{
	freopen("sprime.in","r",stdin);
	freopen("sprime.out","w",stdout);
	cin>>n;
	for(int i=0;i<4;i++)
	{
		s[0]=p1[i];
		dfs(1);
	}
	return 0;
}
bool isprime(int t)
{
	double s=t;
	int t1=(int)sqrt(s);
	for(int i=2;i<=t1;i++)
		if(t%i==0)return false;
	return true;
}
void dfs(int d)
{
	if(d==n)
	{
		cout<<s<<endl;
		return;
	}
	for(int i=0;i<5;i++)
	{
		s[d]=p2[i];
		s[d+1]='\0';
		int t=atoi(s);
		if(isprime(t))dfs(d+1);
	}
}