USACO1.6 回文质数 Prime Palindromes

题目的提示已经非常明显了，可以先生成回文数再判断质数，因为生成回文数的复杂度较小。判断质数用了之前学到的那种做法。

其实可以用一些比较优秀的筛质数的方法，再判断回文数。

 /*

 ID: Starry21

 LANG: C++

 TASK: numtri

 */

 #include<iostream>

 #include<string>

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define N 1005

 #define ll long long

 #define INF 0x3f3f3f3f

 int a,b;

 bool pd(int x)

 {

     if(x==) return ;

     if(x==||x==) return ;

     if(x%!=&&x%!=) return ;

     int s=sqrt(x);

     for(int i=;i<=s;i+=)

         if(x%i==||x%(i+)==)

             return ;

     return ;

 }

 int main()

 {

     //freopen("numtri.in","r",stdin);

     //freopen("numtri.out","w",stdout);

     scanf("%d %d",&a,&b);

     if(a<)

     {

         if(a<=) puts("");

         if(a<=) puts("");

         if(a<=) puts("");

         if(a<=) puts("");

     }

     if(a<=) puts("");

     if(a<)

     {

         for(int i=;i<=;i+=)

             for(int j=;j<=;j++)

             {

                 int t=i*+j*+i;

                 if(pd(t)&&a<=t&&t<=b)

                     printf("%d\n",t);

             }

     }

     if(a<)

     {

         for(int i=;i<=;i+=)

             for(int j=;j<=;j++)

                 for(int k=;k<=;k++)

                 {

                     int t=i*+j*+k*+j*+i;

                     if(pd(t)&&a<=t&&t<=b)

                         printf("%d\n",t);

                 }

     }

     if(a<)

     {

         for(int i=;i<=;i+=)

             for(int j=;j<=;j++)

                 for(int k=;k<=;k++)

                     for(int q=;q<=;q++)

                     {

                         int t=i*+j*+k*+q*+k*+j*+i;

                         if(pd(t)&&a<=t&&t<=b)

                             printf("%d\n",t);

                     }

     }

     return ;

 }

Code

写法比较暴力，基本上参照USACO的提示。

可以知道如果回文数的位数是偶数，那么一定是合数，因为它能够被$11$整除（奇数位的和与偶数位的和是相等的）

当然，也可以打表，$O(1)$查询（误）。

#include<cstdio>

const int num=;

const int p[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

int a,b;

int main()

{

    scanf("%d %d",&a,&b);

    for(int i=;i<=num;i++)

        if(p[i]>=a&&p[i]<=b)

            printf("%d\n",p[i]);

    return ;

}

/*#include<cstdio>

#include<cmath>

using namespace std;

int a,b;

bool check(int x)

{

    if(x==1) return 0;

    for(int i=2;i<=sqrt(x);i++)

        if(x%i==0)

            return 0;

    return 1;

}

bool pd(int x)

{

    int t=x,cnt=0,res=0;

    while(t)

    {

        res=res*10+t%10;

        t/=10;

        cnt++;

    }

    if(cnt%2==0||res!=x) return 0;

    return 1;

}

int main()

{

    int tot=0;

    freopen("1.txt","w",stdout);

    //scanf("%d %d",&a,&b);

    for(int i=5;i<=100000000;i++)

        if(pd(i))

            if(check(i))

            {

                printf("%d,",i);

                tot++;

            }

    printf("\n%d\n",tot);

    return 0;

}*/

巴特西

USACO1.6 回文质数 Prime Palindromes

最新文章

热门文章