C/C++实现回文质数（超详解）

2022-04-14 1350

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 题目链接题目描述输入样例题解部分完整代码未完待续参考文章

唤我沈七就行嘿嘿。

大一软件工程在读。

菜鸡蒟蒻想在博客中记录一些算法学习的心得体会，会持续更新C/C++方面的题解，方便理清思路和日后复习。如果还能结识一起敲代码的小伙伴的话就更好啦嘿嘿，因为笔者实在是太弱了，肯定免不了错误百出。

欢迎批评指正，期待共同成长！

题目链接

题目描述

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

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

输入样例

输入

5 500

输出

题解部分

涉及算法：数论、线性筛、回文数

针对线性筛我已经在上篇博客进行了详细讲解，建议读者在阅读下文题解之前在复习一遍。

算法模板：数论之质数全家桶（内含埃氏筛法，欧拉线性筛法模板）

思路

1.题目的亿级别的数据,说明暴力枚举，即试除法求素数，必然超时。这时我们的线性筛模板就派上了用场。

#define N 100000010
int cnt;//计数
int p[N];//存放质数
bool st[N];//用来筛掉合数，也可以用整型数组代替，1相当于true，0相当false
void get_prime(int n) {
    for(int i = 2; i <= n; i++) {
        if(!st[i]) p[cnt++] = i;
        for(int j = 0; p[j] <= n / i; j++) {
            //对于任意一个合数n，假设pj为n最小质因子，当i<=n/p[j]时，一定会被筛掉
            //因为i枚举到n之前,一定会枚举到n/p[j],而当n/p[j]不就是合数n的因子，
            //所以x一定会被在i<=n/p[j]时被筛除。
            st[p[j]*i] = true;
            if(i % p[j] == 0) break;       
        }
    }
}

2 . 那回文数如何判断呢？

既然是回文数即正着读和倒着读一样，

那我们就把要判断的数倒置之后再和倒置之前的数判断是否相等，

若相等即为回文数。

int a,b,c;
  while(a1)
    {
    b=a%10;
    c=c*10+b;
    a/=10;
    }
    if(c==p[i])
    printf("%d\n",p[i]);

3 .我们将前面提到的两点进行合并，即在指定区间用线性筛之后将质数存贮起来，在判断是否为回文数，整理成程序提交后，发现还是TLE（超时）了一个测试点。

要知道我们使用可是最快的线性筛，那怎么样进一步优化呢？

我们又需要用到一个新的知识点，

除了11以外，一个数的位数是偶数的话，不可能为回文数素数。

 证明
 如果一个回文素数的位数是偶数，则它的奇数位上的数字和与偶数位上的数字和必然相等；
 根据数的整除性理论，容易判断这样的数肯定能被11整除，所以它就不可能是素数

有了这一结论，事情就变的简单了，我们只需要在判断小于8位数的数是否为素数即可。

做法是需要在线性筛判断上加一个特判。

void  get_prime(int n)
{
  for( int i=2;i<=n;i++)
  {
  if(i>10000000)
  continue;
  else
  {
    if(!a[i])p[t++]=i;
    for(int j=0;p[j]<=n/i;j++)
    {
    a[i*p[j]]=true;
    if(i%p[j]==0)break;
    }
  }  
  }  
}

ok核心部分已经讲解完毕，下面奉上完整代码。

完整代码

C++版

#include<bits/stdc++.h>
#define N 100000010
using namespace std;
int p[N],t;
bool st[N];
void  get_prime(int n)
{
  for( int i=2;i<=n;i++)
  {
  if(i>10000000)
  continue;
  else
  {
    if(!st[i])p[t++]=i;
  for(int j=0;p[j]<=n/i;j++)
  {
    st[i*p[j]]=true;
    if(i%p[j]==0)break;
  }
  }  
  }  
}
int main()
{
  int i,j;
  int m,n;
  int a,b,c=0;
  scanf("%d%d",&m,&n);
  get_prime(n);
  for(i=0;i<t;i++)
  { 
  a=p[i];
  if(a<m)
  continue;
    c=0;
    while(a)
    {
    b=a%10;
    c=c*10+b;
    a/=10;
    }
    if(c==p[i])
    printf("%d\n",p[i]);
  }
  return 0;
}

C语言版

#include<stdio.h>
#define N 100000010
int p[N],t;
int st[N];
void  get_prime(int n)
{
  for( int i=2;i<=n;i++)
  {
  if(i>10000000)
  continue;
  else
  {
    if(!st[i])p[t++]=i;
  for(int j=0;p[j]<=n/i;j++)
  {
    st[i*p[j]]=1;
    if(i%p[j]==0)break;
  }
  }  
  }  
}
int main()
{
  int i,j;
  int m,n;
  int a,b,c=0;
  scanf("%d%d",&m,&n);
  get_prime(n);
  for(i=0;i<t;i++)
  { 
  a=p[i];
  if(a<m)
  continue;
    c=0;
    while(a)
    {
    b=a%10;
    c=c*10+b;
    a/=10;
    }
    if(c==p[i])
    printf("%d\n",p[i]);
  }
  return 0;
}