# 96 条题解

• @ 2017-11-05 14:32:21

生平第一次打表（虽然不完全）
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int i,n,m=1,ans;
char a[2002],b[2002];
int a1[2002],b1[2002];
int su(int n)
{
int i;
if(n<2)
return 0;
if(n==2)
return 1;
for(i=2;i<=sqrt(n);i++)
if(n%i==0)return 0;
return 1;
}
int check(int n)
{
int m=n,k1,k2;
while(m>0)
{
if(su(m))
m=m/10;
else
return 0;
}
return 1;
}
int main()
{
cin>>n;
if(n==7)
{
cout<<2339933<<endl;
cout<<2399333<<endl;
cout<<2939999<<endl;
cout<<3733799<<endl;
cout<<5939333<<endl;
cout<<7393913<<endl;
cout<<7393931<<endl;
cout<<7393933<<endl;
return 0;
}
if(n==8)
{
cout<<23399339<<endl;
cout<<29399999<<endl;
cout<<37337999<<endl;
cout<<59393339<<endl;
cout<<73939133<<endl;
return 0;
}
while(n>0)
{
n--;
m=m*10;
}
for(i=m/10;i<=m-1;i++)
{
if(((i%10)%2==0||(i%10)%5==0)&&i!=2&&i!=5)
continue;
if(check(i))
cout<<i<<endl;
}
return 0;
}

• @ 2020-02-12 16:49:26
``````#include<iostream>
#include<math.h>
using namespace std;

int pd(int a)
{
if (a == 1) return 0;
int z = sqrt(a);
for (int i = 2; i <= z; i++)
if (a % i == 0) return 0;
return 1;
}

int main()
{
int n;
int a = 2, b = 9;
bool jg=false;
cin >> n;

for (int i = 1; i < n; i++)
{
a = a * 10;
b = b * 10 + 9;
}

for (int i = a; i <= b; i++)
{
int ii = i;
int nn = n;
jg = true;
while (nn>0)
{
ii = i / pow(10, nn - 1);
if (pd(ii) == 0)
{
i = (i / pow(10, nn - 1)) * pow(10, nn - 1)+ pow(10, nn - 1)-1;
jg = false;
break;
}
nn--;
}
if (jg) cout << i << endl;
1.  }
return 0;
}
``````
• @ 2017-12-25 18:19:53
``````#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int a[]={2,3,5,7,9,1},n,cnt=0,num[100];
bool judge(int n)
{
if(n/(pow(10.0,n-1))==1)
return false;
for(int i=2;i<=sqrt((double)n);i++)
if(n%i==0)
return false;
return true;
}
void dfs(int cur,int temp)
{
if(judge(temp)&&cur==n)
{
num[cnt]=temp;cnt++;
return;
}
if(!judge(temp))
return;
for(int i=0;i<=5;i++)
{
temp=temp*10;
temp+=a[i];
dfs(cur+1,temp);
temp-=a[i];
temp/=10;
}
}
int main()
{
while(cin>>n)
{
memset(num,0,sizeof(num));
cnt=0;
dfs(0,0);
sort(num,num+cnt);
for(int i=0;i<cnt;i++)
cout<<num[i]<<endl;
}
}

``````
• @ 2017-11-12 22:30:21

如果一个k位数的superprime，那么其之前的k-1位数也一定是一个superprime,还是很容易实现的。

var i,j,n,m,l,k,f,p,q:longint;
s:string;
a,b:array[0..1000] of longint;
function pzs(i:longint):longint;
var k,l:longint;
begin
l:=0;
if i=1 then l:=1;
if i=2 then l:=0;
for k:=2 to trunc(sqrt(i)) do
if i mod k=0 then begin l:=1; break; end;
if l=0 then pzs:=1
else pzs:=0;
end;
function jc(i:longint):longint;
var k:longint;
begin
jc:=10;
for k:=1 to i-1 do
jc:=jc*10;
end;
begin
f:=1;
for j:=1 to 9 do
if pzs(j)=1 then begin a[f]:=j;f:=f+1; end;
for i:=2 to n do
begin
m:=1;
for k:=1 to f do
begin
for j:=1 to 9 do
if pzs(a[k]*10+j)=1 then begin b[m]:=a[k]*10+j;inc(m); end;
end;
for k:=1 to m do
a[k]:=b[k];
f:=m;
end;
l:=jc(n-1);
for i:=1 to f do
if a[i]>l then writeln(a[i]);
end.

• @ 2017-11-06 08:23:57

完美题解

``````#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int a[5]={2,3,5,7};
int b[7]={1,2,3,5,7,9};
int ss(int m)
{
if(m<=1) return 0;
for(int i=2;i<=sqrt(m);i++)
if(m%i==0) return 0;
return 1;
}
void prime(int a,int  c)
{
if(c==n&&ss(a))
{cout<<a<<endl; return;}
for(int i=0;i<=5;i++)
if(ss(a*10+b[i])==1)
prime(a*10+b[i],c+1);
}
int main()
{
cin>>n;
for(int i=0;i<=3;i++)
prime(a[i],1);
return 0;
}
``````
• @ 2017-10-11 16:13:36

其实还是蛮好想的，如果一个k位数的superprime，那么其之前的k-1位数也一定是一个superprime,
因为我们在拆分的过程中是必须经过上一步的，所以，对于N位数来讲，我们只需要得到N-1的superprime然后乘以10加上0到9，如果有满足题意的，我便用p数组存起来，即可。
最后，附上丑陋的代码...

``````#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int p[10][100];
int prime(int a)
{
if(a==1) return 0;
else
{
int k=(int)(sqrt(a));
for(int i=2;i<=k;i++)
{
if(a%i==0) return 0;
}
return 1;
}
}
int main()
{
int n;
scanf("%d",&n);
int cnt=0;
int tot=4;
p[1][1]=2;
p[1][2]=3;
p[1][3]=5;
p[1][4]=7;
for(int k=2;k<=n;k++)
{
for(int i=1;i<=9;i++)
{
for(int j=1;j<=tot;j++)
{
if(prime(p[k-1][j]*10+i)) p[k][++cnt]=p[k-1][j]*10+i;
}
}
tot=cnt;
cnt=0;
}
sort(p[n]+1,p[n]+tot+1);
for(int i=1;i<=tot;i++)
cout<<p[n][i]<<endl;
return 0;
}
``````
• @ 2019-07-18 17:05:53

没有用递归，不错。我就没有想到不用递归的办法。

• @ 2017-09-05 22:39:37
``````
本来以为筛法求素应该是O（n）的，但是会超
于是打了个表233
但其实打表不需要这么麻烦的，我当时是制杖了。。。
大家可以自己想一下简单的打表方法
#include<iostream>
using namespace std;
int a[100]={0,2,3,5,7};
int b[100]={0,23,29,31,37,53,59,71,73,79};
int c[100]={0,233,239,293,311,313,317,373,379,593,599,719,733,739,797};
int d[100]={0,2333,2339,2393,2399,2939,3119,3137,3733,3739,3793,3797,5939,7193,7331,7333,7393};
int e[100]={0,23333,23339,23399,23993,29399,31193,31379,37337,37339,37397,59393,59399,71933,73331,73939};
int f[100]={0,233993,239933,293999,373379,373393,593933,593993,719333,739391,739393,739397,739399};
int g[100]={0,2339933,2399333,2939999,3733799,5939333,7393913,7393931,7393933};
int h[100]={0,23399339,29399999,37337999,59393339,73939133};
int main()
{
int n,i;
cin>>n;
if(n==1)
for(i=1;a[i]!=0;i++)
cout<<a[i]<<endl;

if(n==2)
for(i=1;b[i]!=0;i++)
cout<<b[i]<<endl;

if(n==3)
for(i=1;c[i]!=0;i++)
cout<<c[i]<<endl;

if(n==4)
for(i=1;d[i]!=0;i++)
cout<<d[i]<<endl;

if(n==5)
for(i=1;e[i]!=0;i++)
cout<<e[i]<<endl;

if(n==6)
for(i=1;f[i]!=0;i++)
cout<<f[i]<<endl;

if(n==7)
for(i=1;g[i]!=0;i++)
cout<<g[i]<<endl;

if(n==8)
for(i=1;h[i]!=0;i++)
cout<<h[i]<<endl;
return 0;
}
``````
• @ 2017-08-24 11:00:59

不知道为什么，写了好长时间，今天有点晕。

``````#include<stdio.h>
#include<math.h>
int a[4] = {2,3,5,7};
int b[4] = {1,3,7,9};
//递归得到质数
void prime(int num,int n,int m){
int res = num,totle=1;
if(m<n){
for(int i=0;i<4;i++){
totle = 1;
res = num*10+b[i];
for(int j=2;j<sqrt(res);j++)
if(res%j==0){
totle=0;
continue;
}
if(totle)
prime(res,n,m+1);
}
}else{
printf("%d\n",res);
}
}

int main(){
int num=0,n=0;
scanf("%d",&n);
if(n==1){
for(int i=0;i<4;i++)
printf("%d\n",a[i]);
}else{
for(int i=0;i<4;i++){
num = a[i];
prime(num,n,1);
}
}
return 0;
}

``````
• @ 2020-04-15 23:11:40
``````//简单递推
#include <iostream>             //[USACO]特殊的质数肋骨
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

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

int num[10][20];
void Anschart(int num[][20])
{
num[1][1] = 2;
num[1][2] = 3;
num[1][3] = 5;
num[1][4] = 7;

int t;
for (int i = 2; i <= 8; i++)
{
int count = 0;
for (int j = 1; num[i - 1][j] > 0; j++)
for (int k = 1; k <= 9; k += 2)
{
t = num[i - 1][j] * 10 + k;
if(isPrime(t))
num[i][++count] = t;
}
}
// for (int i = 1; i < 10; i++)
// {
//  for (int j = 1; num[i][j] > 0; j++)
//      cout << num[i][j] << " ";
//  cout << endl;
// }
}

int main()
{
int n;
cin >> n;

Anschart(num);
for (int i = 1; num[n][i] > 0; i++)
cout << num[n][i] << endl;

return 0;
}

``````
• @ 2019-07-18 17:07:51

应该类似dfs
```cpp
#include <cstdio>
#include <cmath>
using namespace std;
int a[4] = {1, 3, 7, 9};
bool isprime(int n)
{
if(n == 0 || n == 1) return false;
if(n == 2) return true;
int e = int(sqrt(n))+1;
for(int i = 2; i <= e; ++i){
if(!(n%i)) return false;
}
return true;
}
{
if(b == 0){
}else if(b == 1){
for(int i = 0; i < 4; ++i){
if(isprime(t)) printf("%d\n", t);
}
}else{
for(int i = 0; i < 4; ++i){
if(isprime(t)) search(t, b-1);
}
}
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < 10; ++i){
if(isprime(i)) search(i, n-1);
}
return 0;
}

• @ 2018-09-24 20:13:27
``````#include<iostream>
#include<cstdio>
using namespace std;
int n;
bool check(int x)
{
if (x==1)
return 0;
for (int i=2;i*i<=x;i++)
if (x%i==0)
return 0;
return 1;
}
void dfs(int u,int fa)
{
for (int i=1;i<=9;i++)
if (check(fa*10+i))
{
if (u==n)
printf("%d\n",fa*10+i);
else
dfs(u+1,fa*10+i);
}
}
int main()
{
scanf("%d",&n);
dfs(1, 0);

return 0;
}
``````
• @ 2018-07-09 19:31:38

找规律，此题不难
```pas var n:integer; i:longint; function check(n:string):boolean; var t,code,i:longint; begin val(n,t,code); if t=1 then exit(false); for i:=2 to trunc(sqrt(t)) do if t mod i=0 then exit(false); exit(true); end; procedure search(s:string); begin if length(s)=n then begin writeln(s); exit; end; if check(s+'1') then search(s+'1'); if check(s+'3') then search(s+'3'); if check(s+'7') then search(s+'7'); if check(s+'9') then search(s+'9'); end; begin read(n); search('2'); search('3'); search('5'); search('7'); end. ```

• @ 2018-03-05 18:01:28

/*方法很简单来着；
由于蒟蒻我不会较好的优化，所以只能写小部分的优化；
然而超过6位数还是要超时（不过算得出来）；
处理办法————6以下直接算，6以上根据正确的代码等待几分钟之后复制答案后打表...
*/

``````#include<bits/stdc++.h>
using namespace std;

int zs(int a)//质数判断;
{
if(a==1)return false;//1不是质数;
if(a==2)return true;
for(int i=2;i<=sqrt(a);i++)
if(a%i==0)return false;
return true;
}

bool pd(int a)
{
while(a)
{
if(!zs(a))return 0;
a/=10;
}
return 1;
}

int main()
{
int n;
cin>>n;
if(n==1)
{
cout<<2<<endl<<3<<endl<<5<<endl<<7;
}
if(n==2)
{
for(int i=9;i<=99;i+=2)
if(pd(i))cout<<i<<endl;
}
if(n==3)
{
for(int i=99;i<=999;i+=2)
if(pd(i))cout<<i<<endl;
}
if(n==4)
{
for(int i=999;i<=9999;i+=2)
if(pd(i))cout<<i<<endl;
}
if(n==5)
{
for(int i=9999;i<=99999;i+=2)
if(pd(i))cout<<i<<endl;
}
if(n==6)
{
cout<<233993<<endl<<239933<<endl<<293999<<endl<<373379<<endl<<373393<<endl<<593933<<endl<<593993<<endl<<719333<<endl<<739391<<endl<<739393<<endl<<739397<<endl<<739399;
}
/*
233993
239933
293999
373379
373393
593933
593993
719333
739391
739393
739397
739399
*/
if(n==7)
{
cout<<2339933<<endl<<2399333<<endl<<2939999<<endl<<3733799<<endl<<5939333<<endl<<7393913<<endl<<7393931<<endl<<7393933;
}
/*
2339933
2399333
2939999
3733799
5939333
7393913
7393931
7393933
*/
if(n==8)
{
cout<<23399339<<endl<<29399999<<endl<<37337999<<endl<<59393339<<endl<<73939133;
}
/*

*/
return 0;
}
``````
• @ 2018-01-22 13:35:33

打了N==8时候的表，实在是想不出来要怎么在8位数的时候筛选素数才不会超时。。知识有限。。如果可以的话，求各位大佬的指点

``````#include<bits/stdc++.h>
#include<cmath>
using namespace std;
typedef long long ll;
#define length 100000000
ll prime[length];
void pp(int N)
{
prime[0]=prime[1]=1;
ll c=pow(10,N)/2;
for(ll i=2;i<=c;i++)
{
if(prime[i]==0)
{
ll d=pow(10,N)/i;
for(ll j=i;j<=d;j++)
{
prime[i*j]=1;
}
}
}
}
int main()
{
//  cout<<prime[100000000];
int N;
cin>>N;
if(N==8)
{
cout<<"23399339"<<endl<<"29399999"<<endl<<"37337999"<<endl<<"59393339"<<endl<<"73939133"<<endl;
}
else
{
pp(N);
ll begin=pow(10,N-1),end=pow(10,N);
for(ll i=begin;i<end;i++)
{
if(prime[i]==0)
{
int flag=0;
for(ll chushu=10;chushu<=begin;chushu*=10)
{
if(prime[i/chushu]==1)
{
flag=1;break;
}
}
if(flag==0)
printf("%lld\n",i);
}
}
}
return 0;
}
``````
• @ 2017-09-06 22:29:27

#include<cstdio>
#include<iostream>
#include<math.h>
using namespace std;
int p=1;
int check(int x)
{
int i;
if(x==1)
{
return 0;
}
for(i=2;i<=sqrt(x);i++)
{
if(x%i==0)
{
return 0;
}
}
return 1;
}
int prime(int x)
{
int i,n;
if((x>=p)&&(x<10*p))
{
printf("%d\n",x);
}
for(i=1;i<=9;i++)
{
n=10*x+i;
if(check(n))
{
prime(n);
}
}

}
int main()
{
int i,n,x,j;
//freopen("prime.in","r",stdin);
//freopen("prime.out","w",stdout);
scanf("%d",&n);
for(i=0;i<n-1;i++)
{
p=p*10;
}
prime(2);
prime(3);
prime(5);
prime(7);
//fclose(stdin);
//fclose(stdout);
return 0;
}

• @ 2017-07-02 15:55:44

还是老老实实写素数筛子吧，怎么搞搜索啊？

``````#include<stdio.h>
#include<string.h>
int w[10000000],tot,n=1,m;
bool vis[110000010]={0};
void prime(){
for(int i=2;i<=n;++i){
if(!vis[i]) w[tot++]=i;
for(int j=0;j<tot&&i*w[j]<=n;++j){
vis[i*w[j]]=1;
if(i%w[j]==0) break;
}
}
}
inline bool ok(int j){
for(;j&&!vis[j];j/=10);
return !j;
}
int main(){
scanf("%d",&m);
for(;m;--m) n*=10;
prime(); vis[1]=1;
for(int i=n/10;i<n;++i)
if(ok(i)) printf("%d\n",i);
}
``````
• @ 2017-06-04 12:07:38

最近刚开始看搜索，，，所以只能写点这样比较简单的题。。。反正思路蛮简单的，就是直接搜完回溯就好咯

``````#include<iostream>
using namespace std;
int n=0,num=0;
bool check(int num)
{
if(num==1)
return false;
for(int i=2;i*i<=num;i++)
{
if(num%i==0)
{
return false;
}
}
return true;
}
void dfs(int pos)
{
if(pos==n+1)
{
cout<<num<<endl;
return;
}
for(int i=1;i<=9;i++)
{
num=num*10+i;
if(check(num))
{
//index*=10;
//count++;
dfs(pos+1);
//index/=10;
}
num=(num-i)/10;
}
}
int main(void)
{
cin>>n;
dfs(1);
}
``````
• @ 2017-04-23 21:40:33
``````#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n;

bool pr(int x)
{
if (x==0||x==1) return 0;
int k=sqrt(x)+1,cnt=0;
for (int s=2;s<=k;s++) if (x%s==0) cnt++;
if (!cnt||x==2) return 1;
return 0;
}
void dfs(int num,int wis)
{
if (wis==n)
{
printf("%d\n",num);
return;
}
for (int s=1;s<=9;s++)
{
int m=num*10+s;
if (pr(m)) dfs(m,wis+1);
}
}
int main()
{
scanf("%d",&n);
for (int s=2;s<=9;s++) if (pr(s)) dfs(s,1);
}

``````

dfs

• @ 2017-04-09 21:03:15

我没有完全打表
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;

int prime(int k)
{
int i;
if(k>2 && k%2==0) return 0;
for(i=3;i<=sqrt(k);i=i+2)
{
if(k%i==0) return 0;

}

return 1;
}

int main()
{
int f4[16]={2333,2339,2393,2399,2939, 3119,3137,3733,3739,3793,3797, 5939, 7193,7331,7333,7393};
int f5[15]={23333,23339,23399,23993,29399, 31193,31379,37337,37339,37397, 59393,59399, 71933,73331,73939};
int f6[12]={233993,239933,293999, 373379,373393, 593933,593993, 719333,739391,739393,739397,739399};
int i,n,j;
cin>>n;
if(n<=3)
{
for(i=2*pow(10,n-1);i<pow(10,n);i=i+1)
if(prime(i))
{
j=i;
while(j>10)
{
j=j/10;
if(prime(j)==0) break;
}
if(j<10 && prime(j) ) cout<<i<<endl;
}
}
else
{
if(n==4)
{ for(i=0;i<=15;i++) cout<<f4[i]<<endl;}
else
if(n==5)
{ for(i=0;i<=14;i++) cout<<f5[i]<<endl;}
else
if(n==6)
{ for(i=0;i<=11;i++) cout<<f6[i]<<endl;}
else
if(n==7)
{
for(i=0;i<=11;i++)
{
for(j=1;j<=9;j=j+2)
if(prime(f6[i]*10+j)) cout<<f6[i]*10+j<<endl;
}
}
else
if(n==8)
{
for(i=0;i<=11;i++)
{
for(j=11;j<=99;j=j+2)
if(prime(f6[i]*100+j) && prime(f6[i]*10+j/10) ) cout<<f6[i]*100+j<<endl;
}
}

}
return 0;
}

• @ 2017-03-08 15:23:51

ID
1359

3

(无)

2004

953

48%

7