0586:Palindrome

桁数が2nまたは2n+1の回文素数の中で最大のものを
求める問題。その桁数の回文素数がなかった場合、
その桁数の最大の数を出力する。

桁数が偶数の回文数は11の倍数となるので、
n>1 かつ c<0 の時2n個の９を出力。
それ以外はその桁の大きい回文数から順に素数判定した。

#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<algorithm>
#include <sstream>
 
using namespace std;
 
bool is_prime(int n){
 
  for(int i=2; i*i<=n; i++)
    if(n%i==0)return false;
  return true;
}
 
string toString(int a){
  ostringstream oss;
  oss << a;
  return oss.str();
}
 
int toInt(string s){
  istringstream iss(s);
  int a;
  iss >> a;
  return a;
}
 
int main(void){
  int n,c;
  string str="",C="";
 
  cin >> n >> c;
 
  for(int i=0;i<n;i++)str+="9";
   
  C=c+'0';
 
  if(c<0 && n>1){
    cout << str << str << endl;
    return 0;
  }

  while(true){
    string rstr=str;
    reverse(rstr.begin(),rstr.end());
     
    string res=str+C+rstr;
    int ans=toInt(res);
 
    if(is_prime(ans)){
      cout << ans << endl;
      return 0;
    }
    int tmp=toInt(str);
    tmp--;
    str=toString(tmp);
  }
  return 0;
}