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

[USACO1.5]回文质数 Prime Palindromes

题目描述

因为 $151$ 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 $151$ 是回文质数。

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

5 500

样例输出 #1

5
7
11
101
131
151
181
191
313
353
373
383

提示

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数（素数）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

题目翻译来自NOCOW。

USACO Training Section 1.5

产生长度为 $5$ 的回文数：

for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数for (d2 = 0; d2 <= 9; d2++) {for (d3 = 0; d3 <= 9; d3++) {palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)}}}

代码

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;@SuppressWarnings("all")
public class Main{public static void main(String [] args){Scanner scanner = new Scanner(System.in);int a=scanner.nextInt();int b=scanner.nextInt();if(b>10000000){for(;a<=10000000;a++) {if(symmetry(a)) {if(isPrime(a)){System.out.println(a);}}}}else {for(;a<=b;a++) {if(symmetry(a)) {if(isPrime(a)){System.out.println(a);}}}}}
public static boolean isPrime(int result) {for(int i=2;i<=Math.sqrt(result);i++) {if(result%i==0)	return false;		}return true;
}
public static boolean symmetry(int num) {String temp=String.valueOf(num);StringBuffer a=new StringBuffer(temp);if(temp.equals(a.reverse().toString())) {return true;}	else {return false;}}
}

解析

刚开始的思路就是
1.先判断回文数
2.再判断是否是质数（因为质数肯定比回文数多，提高效率）
刚开始的代码已经忘了

原理的思路就是用我们的StringBuffer的reverse操作判断回文数
但是后三个会超时
所以我们可以分析一下数据范围来缩减我们的判断范围
[a,b] (5≤a<b≤100,000,000)1亿

范围内的最大回文素数为 9989899 ，这个具体怎么算我也不知道，看其他博客的文章看到的
最会加了这个判断刚好过了后三个测试点
如果不用这个条件的话
可以考虑，优化质数判断的时间复杂度可以在本站搜
判断质数和判断回文数最好是另外写一个方法-别问我为什么，我在主程序里写超时，写到别的方法就会提高一点效率