洛谷 P1217 [USACO1.5]回文质数 Prime Palindrome

红太狼 2021-12-21 20:57 214阅读 0赞

## **嗯...** ##

# #

## **这道题对于蒟蒻的我来说实在是TQL...** ##

# #

## **先看一下题：（题目链接：https://www.luogu.org/problemnew/show/P1217）** ##

# **然后说一下我的做题过程吧：** #

### **一看到是普及-的题，就没有考虑什么筛法，只是用最暴力的筛素数的方法做的，然后就导致最后一个点TLE；** ###

### **接着是一个改进，又用了埃氏筛，可是它太不稳定了，然后数组总是开小，然后就各种TLE,MLE,RE...** ###

## **最后用的是欧拉筛（线性筛），然后还是最后一个点TLE...然后就很纳闷，看了题解之后才发现有这样的一个东西：** ##

# **1.偶数位数回文数（除11）必定不是质数（自行百度），所以只要运行到10000000** #

### **然后发现将读入后的b进行一次判断就可以了，然后这种方法，暴力筛还是TLE,埃氏筛由于不稳定也TLE，最终还是只有欧拉筛（线性筛）好用....** ###

# **思路：** #

## **主要是在a到b的这段区间中先判断是否为回文数（注意判断回文数的方法），并且用欧拉筛判断是否为素数即可...** ##

# **重难点：** #

**　　偶数位数回文数（除11）必定不是质数（自行百度），所以只要运行到10000000**

## **否则会一直TLE（不开O2）** ##

# **下面是欧拉筛的AC代码：** #

1 #include<cstdio>
     2 #include<iostream>
     3 
     4 using namespace std;
     5 
     6 int a, b;
     7 const int maxn = 10000005; 
     8 
     9 int cnt;
    10 int prime[maxn];
    11 int vis[maxn];
    12 bool pp[maxn];
    13 
    14 inline void is_prime(){
    15     for(int i = 2; i <= b; i++){
    16         if(!vis[i]) prime[++cnt] = i, pp[i] = 1;
    17         for(int j = 1; j <= cnt && i * prime[j] <= b; j++){
    18                vis[i * prime[j]] = true;
    19             if(i % prime[j] == 0) break;
    20            }
    21        }
    22 }//欧拉筛判断质数 
    23 
    24 inline int hui_wen(int x){
    25     int t = 0;
    26     int y = x;
    27     while(y != 0){
    28         t = t * 10 + y % 10;
    29         y = y / 10;
    30     }
    31     if(t == x) return 1;
    32     return 0;
    33 }//判断回文数 
    34 
    35 int main(){
    36     scanf("%d%d", &a, &b);
    37     if(b > 10000000) b = 10000000;//重点 
    38     is_prime();
    39     for(int i = a; i <= b; i++){
    40         int n = i;
    41         if(hui_wen(n) && pp[n] ) printf("%d\n", n);
    42     }
    43     return 0;
    44 }

转载于:https://www.cnblogs.com/New-ljx/p/10686537.html