96 条题解
-
3
yyyz120 LV 8 @ 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;
} -
1
sq524594846 LV 7 @ 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; } -
1
#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; } } -
1
yangyunsong LV 8 @ 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
readln(n);
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. -
1
完美题解
#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; } -
1
其实还是蛮好想的，如果一个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; }-
nightzy @ 2019-07-18 17:05:53
没有用递归，不错。我就没有想到不用递归的办法。
-
-
1
本来以为筛法求素应该是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; } -
1
不知道为什么，写了好长时间，今天有点晕。
#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; } -
0
//简单递推 #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; } -
0
应该类似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;
}
void search(int head, int b)
{
if(b == 0){
printf("%d\n", head);
}else if(b == 1){
for(int i = 0; i < 4; ++i){
int t = head*10+a[i];
if(isprime(t)) printf("%d\n", t);
}
}else{
for(int i = 0; i < 4; ++i){
int t = head*10+a[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;
} -
0
周煊博 (bill2007) LV 8 @ 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; } -
0
找规律，此题不难
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.
-
0
/*方法很简单来着；
由于蒟蒻我不会较好的优化，所以只能写小部分的优化；
然而超过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; } -
0
打了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; } -
0
Commander_X LV 8 @ 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;
} -
0
还是老老实实写素数筛子吧，怎么搞搜索啊？
#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); } -
0
最近刚开始看搜索，，，所以只能写点这样比较简单的题。。。反正思路蛮简单的，就是直接搜完回溯就好咯
#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); } -
0
#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
-
0
我没有完全打表
#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;
} -
0
yyyz120
LV 8
@ 2017-11-05 14:32:21
