徐州城乡建设局网站,网站层次,免费注册网页网址,怎么做口子推广网站[USACO1.5]回文质数 Prime Palindromes
题目描述
因为 151151151 既是一个质数又是一个回文数#xff08;从左到右和从右到左是看一样的#xff09;#xff0c;所以 151151151 是回文质数。
写一个程序来找出范围 [a,b](5≤ab≤100,000,000)[a,b] (5 \le a b \l…[USACO1.5]回文质数 Prime Palindromes
题目描述
因为 151151151 既是一个质数又是一个回文数从左到右和从右到左是看一样的所以 151151151 是回文质数。
写一个程序来找出范围 [a,b](5≤ab≤100,000,000)[a,b] (5 \le a b \le 100,000,000)[a,b](5≤ab≤100,000,000)一亿间的所有回文质数。
输入格式
第一行输入两个正整数 aaa 和 bbb。
输出格式
输出一个回文质数的列表一行一个。
样例 #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
产生长度为 555 的回文数
for (d1 1; d1 9; d12) { // 只有奇数才会是素数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 ascanner.nextInt();int bscanner.nextInt();if(b10000000){for(;a10000000;a) {if(symmetry(a)) {if(isPrime(a)){System.out.println(a);}}}}else {for(;ab;a) {if(symmetry(a)) {if(isPrime(a)){System.out.println(a);}}}}}
public static boolean isPrime(int result) {for(int i2;iMath.sqrt(result);i) {if(result%i0) return false; }return true;
}
public static boolean symmetry(int num) {String tempString.valueOf(num);StringBuffer anew StringBuffer(temp);if(temp.equals(a.reverse().toString())) {return true;} else {return false;}}
}解析
刚开始的思路就是 1.先判断回文数 2.再判断是否是质数因为质数肯定比回文数多提高效率 刚开始的代码已经忘了
原理的思路就是用我们的StringBuffer的reverse操作判断回文数 但是后三个会超时 所以我们可以分析一下数据范围来缩减我们的判断范围 [a,b] (5≤ab≤100,000,000)1亿
范围内的最大回文素数为 9989899 这个具体怎么算我也不知道看其他博客的文章看到的 最会加了这个判断刚好过了后三个测试点 如果不用这个条件的话 可以考虑优化质数判断的时间复杂度可以在本站搜 判断质数和判断回文数最好是另外写一个方法-别问我为什么我在主程序里写超时写到别的方法就会提高一点效率
