Home > Old Blog Posts > USACO 1.5.3 Superprime Rib

USACO 1.5.3 Superprime Rib


最不厚道但很快很暴力的方法:打表

正规做法就dfs吧,每一层递归都进行一次判断,若没有构成素数就剪掉。

可以继续用miller-rabin装13

代码:

/*
ID: dementr1
PROG: sprime
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
ifstream fin(“sprime.in”);
ofstream fout(“sprime.out”);
int N;
bool judge(int a)
{
if(a==1) return false;
int i;
for(i=2;i<=(int)sqrt(a);i++)
if(a%i==0) return false;
return true;
}
void dfs(int n,int number)
{
int i;
if(judge(number))
{
if(n==N-1) fout<<number<<endl;
else
{
for(i=1;i<=9;i++)
dfs(n+1,number*10+i);
}
}
}
int main()
{
int i;
fin>>N;
for(i=1;i<=9;i++)
dfs(0,i);
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: