嗯...

?

這道題對(duì)于蒟蒻的我來(lái)說(shuō)實(shí)在是TQL...

?

先看一下題：（題目鏈接：https://www.luogu.org/problemnew/show/P1217）

?

然后說(shuō)一下我的做題過(guò)程吧：

?

一看到是普及-的題，就沒(méi)有考慮什么篩法，只是用最暴力的篩素?cái)?shù)的方法做的，然后就導(dǎo)致最后一個(gè)點(diǎn)TLE；

接著是一個(gè)改進(jìn)，又用了埃氏篩，可是它太不穩(wěn)定了，然后數(shù)組總是開(kāi)小，然后就各種TLE,MLE,RE...

最后用的是歐拉篩（線性篩），然后還是最后一個(gè)點(diǎn)TLE...然后就很納悶，看了題解之后才發(fā)現(xiàn)有這樣的一個(gè)東西：

?

1.偶數(shù)位數(shù)回文數(shù)（除11）必定不是質(zhì)數(shù)（自行百度），所以只要運(yùn)行到10000000

?

然后發(fā)現(xiàn)將讀入后的b進(jìn)行一次判斷就可以了，然后這種方法，暴力篩還是TLE,埃氏篩由于不穩(wěn)定也TLE，最終還是只有歐拉篩（線性篩）好用....

?

思路：

主要是在a到b的這段區(qū)間中先判斷是否為回文數(shù)（注意判斷回文數(shù)的方法），并且用歐拉篩判斷是否為素?cái)?shù)即可...

?

重難點(diǎn)：

　　偶數(shù)位數(shù)回文數(shù)（除11）必定不是質(zhì)數(shù)（自行百度），所以只要運(yùn)行到10000000

?

否則會(huì)一直TLE（不開(kāi)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 }//歐拉篩判斷質(zhì)數(shù) 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 }//判斷回文數(shù) 34 35 int main(){ 36 scanf("%d%d", &a, &b); 37 if(b > 10000000) b = 10000000;//重點(diǎn) 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/New-ljx/p/10686537.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P1217 [USACO1.5]回文质数 Prime Palindrome的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。