素数回文（hdu1431）

时间：2021-11-08 02:22:54

素数回文

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9266    Accepted Submission(s): 2167

Problem Description
xiaoou33对既是素数又是回文的数特别感兴趣。比如说151既是素数又是个回文。现在xiaoou333想要你帮助他找出某个范围内的素数回文数，请你写个程序找出 a 跟b 之间满足条件的数。(5 <= a < b <= 100,000,000);
 
Input
这里有许多组数据，每组包括两组数据a跟b。
 
Output
对每一组数据,按从小到大输出a，b之间所有满足条件的素数回文数（包括a跟b）每组数据之后空一行。
 
Sample Input
5 500
 
Sample Output
5
7
11
101
131
151
181
191
313
353
373
383
 
这道题的数据有点大，第一是素数其次是回文数，所以不管哪个都很容易超内存，
所以优化是必须的。
那么就好先了解一下回文数和素数的性质。。。
回文数：偶位数回文数必整除11.先温习一下忘掉多年的知识，
　　　　能整除11的数的条件：数的偶数位和与奇数位和的差可整除11，
　　　　即整个数可以整除11.易证偶位回文数整除11.这样就缩小了查找的范围，
　　　　而且缩小了90%！！！
素数：只能被自身和1整除的数。。。
 

所以；除了11是回文素数以外，其他偶数位回文数均可被11整除并且是合数，

然后就枚举1位3位5位7位9位数的数，然后判断是否为素数即可！！！

本人不才只能想到这菜鸟的思路了，不过浅显易懂啊！o(∩_∩)o 哈哈！

ps：http://acm.hdu.edu.cn/showproblem.php?pid=1431

#include<stdio.h>

__int64 a,b;

bool judge(__int64 x)//判断素数

{

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

        if(x%i==)

            return false;

        return true;

}

void solve()

{

    __int64 ans,i,j,k,m,r;

    if(a<=)    //1位素数和11

    {

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

        {

            if(i>b)

                return ;

            if(judge(i))

                printf("%I64d\n",i);

        }

   }

   if(b>)       //3位数时

   {

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

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

         {

            ans = i*+j*;

            if(ans>=a&&ans<=b&&judge(ans))

                printf("%I64d\n",ans);

            if(ans>=b)

                return;

         }

   }

   if(b>)        //5位数时

   {

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

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

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

               {

                   ans = i*+j*+k*;

                   if(ans>=a&&ans<=b&&judge(ans))

                       printf("%I64d\n",ans);

                   if(ans>=b)

                       return;

               }

   }

   if(b>)         //7位数时

   {

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

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

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

                   for(m=;m<=;m++)

                   {

                       ans = i*+j*+k*+m*;

                       if(ans>=a&&ans<=b&&judge(ans))

                           printf("%I64d\n",ans);

                       if(ans>=b)

                           return;

                   }

   }

   if(b>)       //9位数时

   {

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

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

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

                   for(m=;m<=;m++)

                       for(r=;r<=;r++)

                       {

                           ans = i*+j*+k*+m*+r*;

                           if(ans>=a&&ans<=b&&judge(ans))

                               printf("%I64d\n",ans);

                           if(ans>=b)

                               return;

                       }

   }

}

int main()

{

    while(scanf("%I64d%I64d",&a,&b)!=EOF)

    {

        if(a>b)

        {

            a=a^b;

            b=a^b;

            a=a^b;

        }

        solve();

        printf("\n");

    }

    return ;

}

吐槽：寒假要在家编程真的是。。。。。无力啊！早上又起不来，，，然后关键是心不静啊！(┬＿┬)

相关文章