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

· · 题解

回文质数

顾名思义，回文的质数，先思考:

  1. 暴力枚举[l， r]的没一个数，TLE等着你。。。
  2. 因为判断回文快，而回文数又少，所以先判断回文，再判断质数，恭喜你还是TLE。。。
  3. 有一种玄学的证明方法,有偶数位的回文数（除了11）必然不是质数
    证明方法：显然
    这个数必为11的倍数，小学题，不会的问小学数学老师
  4. 亲测之后，发现以上想法实现后，不用快读快出已经可以过了，但在TLE的边缘徘徊，再想，正偶数（除了2）是不是都不可能是质数呢？时间大约少了一半

    至此，想法已经基本有了，现在代码实现

#include<bits/stdc++.h>
using namespace std;
int l, r;
bool check1(int x)//检查位数
{
    if((1000 <= x && x <= 9999) || (100000 <= x && x <= 999999)) return 0;//不知道&&和||优先级的可以打个括号 
    return 1;
} 
bool check2(int x)//检查是否回文
{
    int a[20], flag = 1;//反正开得下，多开点
    while (x > 0)
    {
        a[flag] = x % 10;
        x /= 10;
        flag++;
    } 
    for (int i = 1; i <= flag / 2; i++)
        if(a[i] != a[flag-i]) return 0;//不符合回文 
    return 1;
} 
bool check3(int x)//检查是否为质数 
{
    if(x == 2) return 1;
    for(int i = 2; i <= sqrt(x); i++)
        if(x % i == 0) return 0;
    return 1;
}
int main()
{
    scanf("%d %d", &l, &r);
    if(l == 2) printf("2\n");//一定要注意2！！！ 
    if(l % 2 == 0) l++; 
    r = min(9999999, r);//再大的数都不可能是回文质数
    for(int i = l; i <= r; i = i + 2)//枚举每一个奇数
    {
        if(check1(i) == 0) continue;
        if(check2(i) == 0) continue;
        if(check3(i) == 0) continue;
        printf("%d\n", i);//printf会比cout快很多 
    }   
    return 0;
}

本人发表的第一篇题解，望点赞!