【USACO 1.5.2】回文质数

时间：2023-02-07 20:59:15

【题目描述】

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

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

【格式】

INPUT FORMAT:

(file pprime.in)

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

OUTPUT FORMAT:

(file pprime.out)

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

【分析】

晕，交了3遍才过。（不要鄙视我了==）

先判断回文数后判断质数。

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 const int Max=;

 using namespace std;

 long long a,b,ans[Max],point=;

 long long mi[]={,,,,,,,,,,10000000000ll};

 void work(long long num,long long len);//len代表的数字的长度

 bool prime(long long num);

 int main()

 {

     //文件操作

     freopen("pprime.in","r",stdin);

     freopen("pprime.out","w",stdout);

     scanf("%lld%lld",&a,&b);

     for (long long i=;i<=;i++)

     {

         work(i,);

         if (i!=) work(i*+i,);

     }

     sort(ans,ans+point);

     for (long long i=;i<point;i++) printf("%lld\n",ans[i]);

     return ;

 }

 bool prime(long long num)

 {

      for (long long i=;i<=(long long)sqrt((double)num)+;i++) if (num%i==) return ;

      return ;

 }

 void work(long long num,long long len)

 {

      if (num>b) return;

      if (num>=a && prime(num)) ans[point++]=num;

      for (long long i=;i<=;i++)

      for (long long j=;j<=;j++)

      {

          if ((len+j*-)<=)

          work(num*mi[j]+i+i*mi[len+j*-],len+j*);

      }

 }

相关文章