题解

96 条题解

  • 3
    @ 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
    @ 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
    @ 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;
        }
    }
    
    
  • 1
    @ 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
    @ 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;
    }
    
  • 1
    @ 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

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

  • 1
    @ 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;
    }
    
  • 1
    @ 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;
    }
    
    
  • 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;
    }
    
    
  • 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;
    }
    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
    @ 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
    @ 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.

  • 0
    @ 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;
    }
    
  • 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;
    }
    
  • 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;
    }

  • 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);
    }
    
  • 0
    @ 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);
    } 
    
  • 0
    @ 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

  • 0
    @ 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;
    }

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

    这是我的题解,大家看一下
    http://blog.csdn.net/qq_35904657/article/details/60872152

信息

ID
1359
难度
3
分类
搜索 | 枚举数论 点击显示
标签
(无)
递交数
2004
已通过
953
通过率
48%
被复制
7
上传者