P1217 [USACO1.5] 回文质数 Prime Palindromes题解

2023-12-20 06:59:03

题目

因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以151是回文质数。

写一个程序来找出范围[a,b](5≤a<b≤100,000,000)(一亿)间的所有回文质数。

输入输出格式

输入格式

第一行输入两个正整数a和b

输出格式

输出一个回文质数的列表,一行一个

代码

#include<bits/stdc++.h>
using namespace std;
bool book[100000001];
void prime(int b){//埃氏筛选法 
    memset(book, true, sizeof(book));
    book[1]=false;
    int n=sqrt(b);
    for(int i=2;i<=n;i++){
        if (book[i]){
            for(int j=2;j<=b/i;j++)//质数的整数倍一定不是质数 
                book[i*j]=false;
        }
    }
}
bool isHWS(int num){
    int temp=num,ans=0;
    while (temp!=0) {
        ans=ans*10+temp%10;
        temp/=10;
    }
    if (ans==num)
        return true;
    else
        return false;
}
int main(){
    int a,b;
    cin>>a>>b;
    //b<=10000000这个判断条件来自:除了11以外,一个数的位数是偶数的话,不可能为回文素数。
    //如果一个回文素数的位数是偶数,则它的奇数位上的数字和与偶数位上的数字和必然相等;
    //根据数的整除性理论,容易判断这样的数肯定能被11整除,所以它就不可能是素数。
    if (b>=10000000)
        b=9999999;
    prime(b);

    if(a>b)
    	return 0;

    if (a%2==0) a++;//除了2以外,2的倍数都不是质数 
    for (int i=a;i<=b;i+=2) {//偶数都不考虑 
        if (book[i] && isHWS(i))
            cout<<i<<endl;
    }
    return 0;
}

文章来源:https://blog.csdn.net/m0_72674633/article/details/135096776
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。