P1217 [USACO1.5]回文质数 Prime Palindromes--java中规中矩解法

r囧r小猫 2022-10-27 02:36 160阅读 0赞

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

[题目链接][Link 1]

## 题目 ##

### 题目描述 ###

> 因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。  
> 写一个程序来找出范围 \[a,b\] (5≤a<b≤100,000,000)( 一亿)间的所有回文质数。

### 输入格式 ###

> 第 1 行: 两个整数 a 和 b .

### 输出格式 ###

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

### 输入输出样例 ###

#### 输入 ####

5 500

#### 输出 ####

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

## 解题思路 ##

### 生成回文数 ###

首先我们了解生成为len长度的回文数的算法，大致思路即我们首先生成长度为len/2长度的所有数据，然后再生成其另外一般拼接即可。注意如果len长度为基数进行一下特殊处理即可。

#### 代码 ####

//生成长度从lowBit--highBit的所有回文
    static public void Huiwen(int lowBit,int highBit){
        
    		for(int len=lowBit;len<=highBit;len++) {
        
    			int mid=len/2;
    			for(int i=(int) Math.pow(10,mid-1);i<Math.pow(10, mid);i++) {
        
    				int pre=i;
    				int last=reverse(pre);
    				if(len%2==1) {
        
    					for(int j=0;j<=9;j++) {
        
    						int curNum=pre*10+j;
    						curNum=curNum*(int)Math.pow(10, mid);
    						curNum+=last;
    					}
    				}
    				else {
        
    					int curNum=pre*(int)Math.pow(10,mid);
    					curNum+=last;
    				}
    			}
    		}
    		return;
    }

**其中curNum代表生成的回文数**

### 判断一个数是否为质数 ###

判断质数的方法有很多,比较简单的就是判断是否能够被除1和其本身外的其他数整除。速度比较快的是筛选法，但是代价是空间复杂度太高可能会出现内存溢出，有兴趣的可以自行查阅相关算法。

#### 代码描述 ####

static boolean isPrime(int n) {
        
    		for(int i=2;i<=(int)Math.sqrt(n);i++) {
        
    			if(n%i==0) return false;
    		}
    		return true;
    	}

### 综合 ###

到此,思路已经清晰,我们需要生成从a到b的所有回文数,然后判断回文数是否为质数,输出即可。

import java.io.*;
    import java.util.*;
    public class Main {
        
    	public static void main(String[] args) throws IOException {
        
    		Scanner sc=new Scanner(System.in);
    		PrintWriter pr=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    		int a=sc.nextInt();
    		int b=sc.nextInt();
    		int lowBit=(int)Math.log10(a)+1;
    		int highBit=(int)Math.log10(b)+1;
    		//生成长度为len的回文质数
    		for(int len=lowBit;len<=highBit;len++) {
        
    			int mid=len/2;
    			for(int i=(int) Math.pow(10,mid-1);i<Math.pow(10, mid);i++) {
        
    				int pre=i;
    				int last=reverse(pre);
    				if(len%2==1) {
        
    					for(int j=0;j<=9;j++) {
        
    						int curNum=pre*10+j;
    						curNum=curNum*(int)Math.pow(10, mid);
    						curNum+=last;
    						if(curNum>=a && curNum<=b && isPrime(curNum)) pr.println(curNum);
    					}
    				}
    				else {
        
    					int curNum=pre*(int)Math.pow(10,mid);
    					curNum+=last;
    					if(curNum>=a && curNum<=b && isPrime(curNum)) pr.println(curNum);
    				}
    			}
    		}
    		pr.flush();
    		return;
    	}
    	static boolean isPrime(int n) {
        
    		for(int i=2;i<=(int)Math.sqrt(n);i++) {
        
    			if(n%i==0) return false;
    		}
    		return true;
    	}
    	static int reverse(int num) {
        
    		int res=0;
    		while(num!=0) {
        
    			res=res*10+num%10;
    			num/=10;
    		}
    		return res;
    	}
    }

[Link 1]: https://www.luogu.com.cn/problem/P1217