我操。。。。总以为判断素数是用高大上的方法。。。没想到直接判就好了，我智障了 这题直接递归的搜索就好了。。。。总想着打表、、、、我服了自己 啊啊啊啊 有没有人交个朋友啊。。。。刷题好无聊啊

MR + DFS
#include"stdio.h"
#include"stdlib.h"
typedef long long ll;
int a[4]={2,3,5,7};
int b[4]={1,3,7,9};

ll mypow(ll a,ll b,ll m)
{
if(b==0)
return 1;
if(b==1)
return a%m;
ll temp=mypow(a,b/2,m);
temp*=temp;
temp%=m;
if(b&1)
temp*=a;
temp%=m;
return temp;
}
bool Miller_Rabbin(ll x)
{
if(x==2)
return true; ///2要直接判断
for(int i=1;i<=50;++i){
ll a=rand()%(x-2)+2;
if(mypow(a,x-1,x)!=1)
return false;
}
return true;
}
int n;
void dfs(int num,int dep)
{
//puts("fuck");
if(dep==n) {printf("%d\n",num);return; } //1,,3,,,7,,9,
for(int i=0;i<4;i++)
if(Miller_Rabbin(num*10+b[i]))
dfs(num*10+b[i],dep+1);
}

int main()
{

int i;
while(scanf("%d",&n)==1)
{
for(i=0;i<4;i++)
dfs(a[i],1);
}
return 0;
}

miller-rabin+dfs秒杀
```c++
#include <bits/stdc++.h>
using namespace std;

#define ll long long
ll pow(ll a, ll n, ll m)
{
if (n == 0) return 1%m;
ll p = pow(a, n>>1, m);
p = (p%m)*(p%m)%m;
if (n&1) p = p%m*a%m;
return p%m;
}

bool is_prime(ll n)
{
for (int i = 1; i <= 10; i++) {
ll a = rand()%(n-1)+1;
//cout << a << endl;
//cout << pow(a, n-1, n) << endl;
if (pow(a, n-1, n) != 1) return 0;
}
return 1;
}

ll table[1001], top = 0;

void dfs(ll k, int bas)
{
if (bas == 1) {
table[++top] = k;
return;
}
for (int i = 1; i <= 9; i+=2)
if(is_prime(k*10+i))
dfs(k*10+i, bas-1);
}

int main()
{
srand(time(0));
int n;
cin >> n;
dfs(2, n);
dfs(3, n);
dfs(5, n);
dfs(7, n);
sort(table+1, table+top+1);
for (int i = 1; i <= top; i++)
printf("%lld\n", table[i]);
return 0;
}
```

#include <cstdio>
#include <cmath>

int n;

int check(int x){
int flag,i;
flag=1;
for(i=2;i<=sqrt(x);i++)
if(x%i==0){
flag=0;
break;
}
return flag;
}

void dfs(int x,int z){ //z位
int r;
if(z==n){
printf("%d\n",x);
return;
}
for(int i=1;i<=9;i++){
r=x*10+i; //最后面加一个数
if(check(r))
dfs(r,z+1);
}
}

int main(void){
scanf("%d",&n);
//注意到10以内的质数为 2 3 5 7
dfs(2,1);
dfs(3,1);
dfs(5,1);
dfs(7,1);
return 0;
}

筛法求素数+dfs

#include <iostream>
#include <cmath>
using namespace std;
int num[10];
int n;
bool isPrime (long a)
{
if (a==1)
return 0;
long c,i;
double d;
d=sqrt(a);
c=floor(d);
for (i=2;i<=c;i++)
if (a%i==0)
return 0;
return 1;
}
int build (int a)
{
int i,ans=0,k=1;
for (i=a;i>=1;i--)
{
ans+=num[i]*k;
k*=10;
}
return ans;
}
void dfs (int a)
{
int i,ll;
bool flag;
if (a==n+1)
{
for (i=1;i<=n;i++)
cout<<num[i];
cout<<endl;
}
for (i=1;i<=9;i++)
{
num[a]=i;
ll=build(a);
flag=isPrime(ll);
if (flag==1)
dfs(a+1);
}
}
int main()
{
cin>>n;
dfs (1);
return 0;
}

uses dos;
var
a,b,r,d:word;
t,n,i:longint;
c:array[1..100000000]of byte;
function prime(n:longint):boolean;
var
i:longint;
begin
if c[n]=2 then
exit(true)
else
if c[n]=1 then
exit(false);
for i:=2 to trunc(sqrt(n))+1 do
if prime(i) then
if n mod i=0 then
begin
c[n]:=1;
exit(false);
end;
c[n]:=2;
exit(true);
end;
function chk(a:longint):boolean;
var
i,t:longint;
k,k2:string;
begin
str(a,k);
for i:=2 to length(k) do
begin
val(k[i],t);
if t mod 2=0 then
exit(false);
end;
for i:=1 to length(k) do
begin
val(copy(k,1,i),t);
if not prime(t) then
exit(false);
end;
exit(true);
end;
begin
c[1]:=1;
c[2]:=2;
readln(n);
t:=1;
for i:=2 to n do
t:=t*10;
i:=t+1;
while i<=t*10-t-1 do
begin
if chk(i) then
writeln(i);
i:=i+2;
if n>2 then
case (i mod 100)div 10 of
2,4,6,8,0:inc(i,10);
end;
if n>3 then
case (i mod 1000)div 100 of
2,4,6,8,0:inc(i,100);
end;
if n>4 then
case (i mod 10000)div 1000 of
2,4,6,8,0:inc(i,1000);
end;
if n>5 then
case(i mod 100000)div 10000 of
2,4,6,8,0:inc(i,10000);
end;
if n>6 then
case(i mod 1000000)div 100000 of
2,4,6,8,0:inc(i,100000);
end;
end;
end.

天呀

a

AC100题纪念。

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

long a[1001];
int su(long x)
{
long i;
for (i=2;i<=floor(sqrt(x));i++)
if (x%i==0) return 0;
return 1;
}

int main()
{
long i,j,jj,n,k,kk,t;
scanf("%d",&n);
k=4;
a[1]=2;
a[2]=3;
a[3]=5;
a[4]=7;
for (i=1;i<n;i++)
{
kk=k;
for (j=1;j<=kk;j++)
for (t=1;t<=9;t++)
if (su(a[j]*10+t)==1)
{
k++;
a[k]=a[j]*10+t;
}
for (j=1;j<=kk;j++) a[j]=0;
for (j=1;j<=k-kk;j++) a[j]=a[j+kk];
k=k-kk;
}
for (i=1;i<=k;i++)
printf("%ld\n",a[i]);
}

直接递归，grow（high，ceng）表示高位为high，要变成high*10+1、high*10+2、high*10+3........
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
bool prime(int n){
if (n == 1)return false;
int i;
for (i = 2; i*i <= n; i++){
if (n%i == 0)return false;
}
return true;
}
void grow(int high, int ceng){
int i;
int now;
for (i = 1; i < 10; i ++){
now = high * 10 + i;
if (prime(now)){
if (ceng == 1)
cout << now << endl;
else
grow(now, ceng - 1);
}
}
}
int main(){
freopen("in.txt", "r", stdin);
int n;
cin >> n;
grow(0, n);
return 0;
}

素数筛表示很难过
不得不递推......

vector<int> d[10];

bool is_prime(int k)
{
for(int i=2,u=(int)sqrt(k);i<=u;i++)
if(k%i==0) return false;
return true;
}

int n;

int main()
{
scanf("%d",&n);

d[0].push_back(2);
d[0].push_back(3);
d[0].push_back(5);
d[0].push_back(7);

for(int i=1;i<n;i++)
{
for(int j=0;j<d[i-1].size();j++)
{
for(int r=0;r<10;r++)
{
int k=d[i-1][j]*10+r;
if(is_prime(k)) d[i].push_back(k);
}
}
}

for(int i=0;i<d[n-1].size();i++)
printf("%d\n",d[n-1][i]);

return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int a[10][50], n, sum, i = 2, j = 1, p = 1;
bool prime(int a)
{
if(a == 1) return false;

if(a!=2)
{for(int i = 2; i * i <= a; i++) if(a % i == 0) return false;}

return true;
}
bool judge(int a, int n)
{
for(int i = 1; i <= n; i++)
{
if(prime(a) == false) return false;

a = a / 10;
}

return true;
}
int main()
{
scanf("%d", &n);
memset(a, 0, sizeof(a));
a[1][1] = 2;
a[1][2] = 3;
a[1][3] = 5;
a[1][4] = 7;

while(i <= n)
{
while(a[i - 1][j] != 0)
{
sum = a[i - 1][j] * 10 + 1;

if(judge(sum, i) == true)
{
a[i][p] = sum;
p++;
}

sum = a[i - 1][j] * 10 + 3;

if(judge(sum, i) == true)
{
a[i][p] = sum;
p++;
}

sum = a[i - 1][j] * 10 + 7;

if(judge(sum, i) == true)
{
a[i][p] = sum;
p++;
}

sum = a[i - 1][j] * 10 + 9;

if(judge(sum, i) == true)
{
a[i][p] = sum;
p++;
}

j++;
}

i++;
j = 1;
p = 1;
}

i = 1;

while(a[n][i] != 0)
{
printf("%d\n", a[n][i]);
i++;
}

return 0;
}

绝妙算法，无视时间限制
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int a[10][50],n,sum,i=2,j=1,p=1;
bool prime(int a)
{
if(a==1) return false;
for(int i=2;i*i<=a;i++)
if(a%i==0)
return false;
return true;

}
bool judge(int a,int n)
{
for(int i=1;i<=n;i++)
{
if(prime(a)==false) return false;
a=a/10;
}
return true;

}
int main()
{
scanf("%d",&n);
memset(a,0,sizeof(a));
a[1][1]=2;
a[1][2]=3;
a[1][3]=5;
a[1][4]=7;
while(i<=n)
{
while(a[i-1][j]!=0)
{
sum=a[i-1][j]*10+1;
if(judge(sum,i)==true)
{
a[i][p]=sum;
p++;

}
sum=a[i-1][j]*10+3;
if(judge(sum,i)==true)
{
a[i][p]=sum;
p++;

}
sum=a[i-1][j]*10+7;
if(judge(sum,i)==true)
{
a[i][p]=sum;
p++;

}
sum=a[i-1][j]*10+9;
if(judge(sum,i)==true)
{
a[i][p]=sum;
p++;

}
j++;

}
i++;
j=1;
p=1;

}
i=1;
while(a[n][i]!=0)
{
printf("%d\n",a[n][i]);
i++;

}
return 0;
}

从第一位是质数开始枚举 然后第二位也是质数 依次类推 可以0ms秒杀

###Block code
/*happywu
* vijos 1359
* 2014.7.5
*/
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
const int a[6]={1,2,3,5,7,9};
int n;
bool pd(int x)
{
if(x==1)return 0;
int k=sqrt(x);
for(int i=2;i<=k;i++)
{
if(x%i==0)return 0;
}
return 1;
}
void search(int now,int len)
{
if(len>n)
{
printf("%d\n",now);
return;
}
int tmp=now;
for(int i=0;i<6;i++)
{
tmp=now*10+a[i];
if(pd(tmp))search(tmp,len+1);
}
}
int main()
{
scanf("%d",&n);
search(0,1);
return 0;
}

5 忘加了。。。AC率。。。。AC 20题纪念

Program p1359;

const a:array[1..6] of integer=(1,2,3,5,7,9);

var n,i,j:integer;

num:longint;

function check(num:longint):boolean;

var i:integer;

begin

for i:=2 to trunc(sqrt(num)) do

if num mod i=0 then

begin

check:=false;

exit;

end;

if num=1 then begin check:=false;exit;end;

check:=true;

end;

procedure find(num:longint;l:integer);

var i:integer;

begin

if not check(num) then exit;

if l=n then begin

writeln(num);

exit;

end;

for i:=1 to 6 do find(num*10+a[i],l+1);

end;

begin

readln(n);

find(0,0);

end.

var n:longint;

　　s:string;

function zs(k:longint):boolean;

var j:longint;

begin

zs:=true;

if k=1 then begin zs:=false; exit; end;

for j:=2 to round(sqrt(k)) do

if k mod j =0 then

begin

zs:=false;

exit;

end;

end;

procedure find(m:integer);

var i,x,t,p:longint;

begin

if m>n then begin writeln(s); exit; end;

for i:=1 to 9 do

begin

t:=0;

p:=1;

for x:=m-1 downto 1 do

begin

p:=p*10;

t:=(ord(s[x])-48)*p+t;

end;

t:=t+i;

if zs(t) then

begin

insert(chr(i+48),s,m);

find(m+1);

delete(s,m,1);

end;

end;

end;

begin

readln(n);

find(1);

end.

超正常！！！！！！！！！！！

打表才是王道

0msAC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

贴下

#include

int main(void)

{

int n;

long min=1;

long max=1;

int i=0;

static long a[150]={2,3,5,7,23,29,31,37,53,59,71,73,79,233,239,293,311,313,317,373,379,59

3,599,719,733,739,797,2333,2339,2393,2399,2939,3119,3137,3733,3739

,3793,3797,5939,7193,7331,7333,7393,23333,23339,23399,23993,29399

,31193,31379,37337,37339,37397,59393,59399,71933,73331,73939,233

993,239933,293999,373379,373393,593933,593993,719333,739391,739

393,739397,739399,2339933,2399333,2939999,3733799,5939333,7393

913,7393931,7393933,23399339,29399999,37337999,59393339,739391

33};

scanf("%d",&n);

for(i=1;i=min&&a[i]

const

a:array[1..4]of integer=(1,3,7,9);

s:array[1..4]of integer=(2,3,5,7);

var n,i:longint;

procedure dfs(i,len:longint);

var j:integer;

begin

for j:=2 to trunc(sqrt(i)) do

if i mod j=0 then exit;

if len=n then begin writeln(i);exit;end;

for j:=1 to 4 do dfs(i*10+a[j],len+1);

end;

begin

readln(n);

for i:=1 to 4 do dfs(s[i],1);

end.