http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2318 
题目:Prime Palindromes 回文质数

题解:这题时间是限制一秒,这是一个用来玩时间的题目,确实好玩,直接暴力的话,肯定
会超时的,呵呵,不要试了,我已经试过很多次了,不过除了三种情况需要注意:

第一:循环时不要判断偶数;
第二:四位以上的数,奇数位才可能有素数,偶数为不可能有素数;
第三:先判断是否是回文,再判断是否是素数,原因自己想.

这样,就不会超时啦,过得相当的勉强,总之一句话,暴力万岁呀cheekycheekycheeky

 

  2318 Accepted 844 kb 932 ms   660 B

代码如下:

#include<stdio.h>
#include<math.h>
int main()
{
    int a,b,c,k,i,j,flag=0;
    char str[11];
    scanf("%d%d",&a,&b);
    if(a%2==0&&a!=2)
        a+=1;
    for(i=a;i<=b;i+=2)//循环每次都保证是奇数
    {
        flag=0;
        c=i;
        j=0;
        /*四,六,八位整数都不可能是素数*/
        if(i>=1000&&i<=10000||i>=100000&&i<=1000000||i>=10000000&&i<=100000000)
            continue;
        while(c)
        {
            str[j++]=c%10;
            c/=10;
        }
        for(k=0;k<j/2;k++)
            if(str[k]!=str[j-k-1])
            {
                flag=1;
                break;
            }
        if(flag)
            continue;
        k=sqrt(i);
        for(j=2;j<=k;j++)
            if(i%j==0)
                break;
        if(j>=k+1)
            printf("%d\n",i);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation