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

柔情只为你懂 2022-06-01 11:44 169阅读 0赞

## 题目描述 ##

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

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

## 输入输出格式 ##

输入格式：

第 1 行: 二个整数 a 和 b .

输出格式：

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

## 输入输出样例 ##

输入样例\#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;//(处理回文数...)

思路根据题目的提示列举回文数，不存在4 6 8等更大偶数位的回文数

#include<stdio.h>
    #include<iostream>
    #include<cstring>
    #include<math.h>
    using namespace std;
    #define maxn 100000000
    int prime[maxn], res;
    bool is_prime[maxn];//is_prime[i]=1则i不是素数，否则是素数
    
    bool pd(int x)           //一般质数判断，不解释
    {
    	int q = (int)sqrt(x);
    	for (int i = 2; i <= q; i++)
    	if (x%i == 0)
    		return 0;
    	return 1;
    }
    
    void get_prime(int n)				
    {
    	res = 0;
    	memset(is_prime, 0, sizeof(is_prime));
    	is_prime[0] = is_prime[1] = 1;
    	for (int i = 2; i <= n;i++)
    	if (!is_prime[i])
    	{
    		//prime[res++] = i;
    		for (int j = 2; j*i <= n; j++) is_prime[j*i] = 1;
    	}
    }
    
    void print(int a,int b,int p)
    {
    	if (p >= a&&p <= b&&pd(p))
    		cout << p << '\n';
    }
    
    int main()
    {
    	int a, b;
    	cin >> a >> b;
    	//get_prime(b);						   //打素数表超时，还是产生一个判一下素数吧
    	int d1, d2, d3, d4;
    	if (a <= 5 && 5 <= b)
    		cout << 5 << '\n';
    	if (a <= 7 && 7 <= b)
    		cout << 7 << '\n';
    	if (a <= 11 && 11 <= b)
    		cout << 11 << '\n';
    
    	for (d1 = 1; d1 <= 9; d1 += 2)			//3和4
    	for (d2 = 0; d2 <= 9; d2++)
    	{
    		print(a, b, d1 * 100 + d2 * 10 + d1);
    		//print(a, b, d1 * 1000 + d2 * 100 + d2 * 10 + d1);
    	}
    
    	for (d1 = 1; d1 <= 9; d1 += 2)			//5和6
    	for (d2 = 0; d2 <= 9; d2++)
    	for (d3 = 0; d3 <= 9; d3++)
    	{
    		print(a, b, 10000 * d1 + 1000 * d2 + 100 * d3 + 10 * d2 + d1);
    		//print(a, b, 100000 * d1 + 10000 * d2 + 1000 * d3 + 100 * d3 + 10*d2+ d1);
    	}
    
    	for (d1 = 1; d1 <= 9; d1 += 2)			//7和8
    	for (d2 = 0; d2 <= 9; d2++)
    	for (d3 = 0; d3 <= 9; d3++)
    	for (d4 = 0; d4 <= 9; d4++)
    	{
    		print(a, b, 1000000 * d1 + 100000 * d2 + 10000 * d3 + 1000 * d4 + 100*d3+10*d2+d1);
    		//print(a, b, 10000000 * d1 + 1000000 * d2 + 100000 * d3 + 10000 * d4 + 1000 * d4 + 100*d3+10*d2+d1);
    	}
    	return 0;
    }

看到大神用回溯法写的，膜一下

[https://www.luogu.org/blog/user22136/solution-p1217][https_www.luogu.org_blog_user22136_solution-p1217]

得知：**ceil(log10(r))是r的位数，学习了**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<string>
    #include<cmath>
    using namespace std;
    int l, r, a[100];
    
    bool pd(int x)           //一般质数判断，不解释
    {
    	int q = (int)sqrt(x);
    	for (int i = 2; i <= q; i++)
    	if (x%i == 0)
    		return 0;
    	return 1;
    }
    
    void put(int n,int len)							//递归产生回文数
    {
    	if (len > (n + 1) / 2)
    	{
    		int s = 0;                             //预备输出
    		for (int i = 1; i <= n / 2; i++)           //把填的数扩展成回文数
    			a[n - i + 1] = a[i];
    		for (int i = 1; i <= n; i++)             //从数组转化为数
    			s = s * 10 + a[i];
    		if (s>r || s<l)                  //如果大了或小了就return（这你完全可以放在前面判断，效率更高）
    			return;
    		if (pd(s))                   //如果s是质数
    			cout << s << endl;          //输出
    	}
    	else
    	{
    		for (int i = (len == 1); i <= 9; i += (len == 1) + 1)
    		{
    			a[len] = i;
    			put(n, len + 1);
    		}
    	}
    }
    
    int main()
    {
    	cin >> l >> r;
    	for (int i = ceil(log10(l)); i <= ceil(log10(r)); i++)			//针对i～j区间的数进行产生，ceil(log10(r))是r的位数
    	{
    		//cout << i << '\n';
    		if (!(i%2==0&&i>2))											//4 6 8 等更大的偶数不会产生回文素数
    		put(i, 1);													//产生
    	}
    	return 0;
    }

[https_www.luogu.org_blog_user22136_solution-p1217]: https://www.luogu.org/blog/user22136/solution-p1217