HDOJ 1431-素数回文【删除大量无关数据】

￡神魔★判官ぃ 2022-07-26 00:07 230阅读 0赞

# 素数回文 #

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 16454 Accepted Submission(s): 3667

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

Author

xiaoou333

Source

[zjut ][zjut]

#include<stdio.h>    
    bool is[9989900];  
    int prime[1000]; 
    
    void set()
    {
        int i,j;   
        i=2;
        for(j=i*i;j<=9989899;j+=i)  //偶数 
            is[j]=true; 
        for(i=3;i<=3163;i=i+2)   
        {   
            if(is[i])
                continue;   
            for(j=i*i;j<=9989899;j+=i)    
                is[j]=true;   
        }   
    }   
    
    bool test(int a) 
    {   
        int temp=a;   
        int b=0;   
        while(temp!=0)   
        {   
            b=b*10;   
            b+=temp%10;   
            temp/=10;   
        }   
        return a==b;   
    }   
    
    int main()   
    {   
        int a,b;   
        int i,k=0;   
        set();   
        for(i=5;i<=9989899;i+=2)   
            if(!is[i]&&test(i))   
                prime[k++]=i;   
            while(~scanf("%d %d",&a,&b))   
            {   
                for(i=0;i<k;i++)   
                {   
                    if(prime[i]<a)   
                        continue;   
                    else if(prime[i]<=b)   
                        printf("%d\n",prime[i]);   
                    else  
                        break;   
                }   
                printf("\n");   
            }   
            return 0;   
    }

[zjut]: http://acm.hdu.edu.cn/search.php?field=problem&key=zjut&source=1&searchmode=source