社区首页 >专栏 ><Sicily>1005. Prime Palindromes质数回文数的判断方法

<Sicily>1005. Prime Palindromes质数回文数的判断方法

梦飞

发布于 2022-06-23 03:32:39

38400

代码可运行

文章被收录于专栏：csdn文章同步csdn文章同步

运行总次数：0

代码可运行

原题如下

1005. Prime Palindromes Time Limit: 1sec Memory Limit:256MB

Description

The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .

简译：找出a到b之间既是回文数又是质数的数。

Input

There are multiple test cases.

Each case contains two integers, a and b.

a=b=0 indicates the end of input.

Output

For each test case, output the list of palindromic primes in numerical order, one per line.

Sample Input Copy

5 500
0 0

Sample Output Copy

思路

首先分成两部分考虑。

回文数

怎么找出a和b之间的回文数？一个个判断？有一个比较快的方法就是构造，因为根据回文数的性质，很容易构造出一定范围内的回文数。比如，用12,可以构造出121和1221；234可以构造出23432和234432。到这里我们大概可以看出规律了，一个n位数可以构造出2n-1或者2n位的回文数。

那从哪个数开始构造起呢？我们可以先计算下限a的位数digit，然后其(digit+1) / 2就是开始构造的数的最小位数，比如a是500，共有3位数，那么就从2位数开始构造起，从10-99可以构造出505，606,999等比500大的回文数，如果还没到达上限，就继续用三位数即100-999构造，直到超出上限为止。

代码如下：

void palindromesBetween(int a, int b){
	// 根据a的位数计算下限 
	int digit = 0; // a 的位数 
	int temp = a;
	while(temp > 0){
		temp = temp / 10;
		digit++;
	}
	int min = 1;
	for(int i = 1; i < (digit + 1) / 2; i++){
		min *= 10;
	}
	for(int low = min; low < b; low *= 10){ // 从最小的数开始构造 
		int res;
		for(int i = 0; i < 2; i++){ // 分两种情况构造 
			for(int num = low; num < low * 10; num++){
				if(i == 0) res = num / 10; // 奇数位数 
				else if(i == 1) res = num; // 偶数位数 
				int n = num;
				while(n > 0){
					res = res * 10 + n % 10;
					n = n / 10;
				}
				if(res > b) break; // 超出上限，停止构造 
				if(res >= a)
					cout << res << endl;
			}
			if(res > b) break;
		}
		if(res > b) break;
	}
}

质数

一个简单的判断方法就是用数x除以2~x/2，如果都不能除尽，则说明x没有除了1和本身之外的因数，则为质数。

但还有另外一个更快的方法，可以跳过很多没必要判断的数。原理是：一个大于等于5的质数一定可以表示为6n+1或6n+5，即除以6的余数一定是1或5。很容易证明，因为显然6n，6n+2，6n+3，6n+4都不是质数。

但形式为6n+1或6n+5的也不一定是质数。并且，如果x是一个质数，那么一定有6n+1或6n+5的形式，所以必定是一个奇数，所以不可能被6n，6n+2，6n+4整除，另外如果x能被6n+3整除，那么一定得是3的倍数，但是6n是3的倍数，所以6n+1和6n+5不可能是6n+3的倍数，即x不可能被6n+3整除。所以只需要判断该数能否被6n+1或6n+5整除即可，即每6个数只需要判断两个数。

此外，其实并不用计算到x/2，因为一个数分解为两个因数，一定有一个大于sqrt(x)，一个小于sqrt(x)，如果在sqrt(x)左侧找不到因数，那右侧肯定也找不到，所以只需要判断到sqrt(x)。

有了这些原理，就可以开始写代码了：

bool isPrime(int num){
	if(num == 2 || num == 3)
		return true; 
	if(num % 6 != 1 && num % 6 != 5){
		return false;
	}
	for(int i = 5; i <= (int)sqrt(num); i += 6){
		if(num % i == 0 || num % (i + 2) == 0){
			return false;
		}
	}
	return true;
}

合并优化

有了以上的方法，合并起来就可以进行题目的求解了。但其实还可以进行优化。

因为一个偶数长度的回文数，一定可以被11整除，所以不可能是质数。原因是11的倍数有一个性质：奇数位上数字之和 = 偶数位上数字之和，逆过来也成立。而偶数长度的回文数一定满足这个性质，因为对称的数位一定一个在奇数位一个在偶数位。

所以其实没必要生成偶数位的回文数，这样可以减少很多计算。

再结合题目的数字范围，整合后的代码如下：

#include <iostream>
#include <math.h>

using namespace std;

bool isPrime(int);

int main(){
	int a, b;
	while(true){
		cin >> a >> b;
		if(b == 0) break;
		// 先输出a到11的质数 
		for(int i = a; i <= 11; i++){
			if(isPrime(i)){
				cout << i << endl;
			}
		}
		// 根据a的位数计算下限 
		int digit = 0; // a 的位数 
		int temp = a;
		while(temp > 0){
			temp = temp / 10;
			digit++;
		}
		int min = 10;
		for(int i = 2; i < (digit + 1) / 2; i++){
			min *= 10;
		}
		for(int low = min; low < b; low *= 10){
			int res;
			for(int num = low; num < low * 10; num++){
				res = num / 10;
				int n = num;
				while(n > 0){
					res = res * 10 + n % 10;
					n = n / 10;
				}
				if(res > b) break;
				if(res >= a && isPrime(res))
					cout << res << endl;
			}
			if(res > b) break;
		}
	}
}

bool isPrime(int num){
	if(num % 6 != 1 && num % 6 != 5){
		return false;
	}
	for(int i = 5; i <= (int)sqrt(num); i += 6){
		if(num % i == 0 || num % (i + 2) == 0){
			return false;
		}
	}
	return true;
}

另外附上判断一个数是否为回文数的方法：思路是把这个数倒过来看是否跟原来相等。

bool isPalindrome(int num){
	int newNum = 0;
	int n = num;
	while(n > 0){
		int r = n % 10;
		n = n / 10;
		newNum = newNum * 10 + r;
	}
	return newNum == num;
}