C++で次の回文素数を見つける

この問題では、要素Nが与えられます。次の回文素数を見つける必要があります。

問題の説明 − Nより大きい、回文数でもある最小の素数を見つける必要があります。

回文数は、両方向で同じ数の数です。

素数は、その唯一の要素が1とそれ自体である場合の数です。

問題を理解するために例を見てみましょう

入力

N = 12

出力

101

説明

12を超える一連の回文は、22、33、44、55、66、77、88、99、101です。これらのうち最小の回文は101です。

ソリューションアプローチ

この問題の簡単な解決策は、素数であるNより大きいすべての回文を見つけることです。

より効率的な解決策は、11の倍数である偶数桁の回文を見つけることです。

これがこのソリューションの証拠です

11% 11 = 0
1111% 11 = 0

これを使用すると、数字が偶数の回文が見つかります-

xyzzyx％11 =0、これによりすべての偶数桁が回文ではなくなります。

ソリューションの動作を説明するプログラム

例

#include <iostream>
#include <string>
using namespace std;
bool isPrime(int num) {
   if (num < 2 || num % 2 == 0)
      return num == 2;
   for (int i = 3; i * i <= num; i += 2)
      if (num % i == 0)
         return false;
   return true;
}
int primePalindrome(int N) {
   if (8 <= N && N <= 11)
      return 11;
   for (int x = 1; x < 100000; ++x) {
      string s = to_string(x), r(s.rbegin(), s.rend());
      int y = stoi(s + r.substr(1));
      if (y >= N && isPrime(y))
         return y;
   }
   return -1;
}
int main() {
   int N = 432;
   cout<<"The next prime palindrome is "<<findNextPrimePallindrome(432);
   return 0;
}

出力

The next number with same set of digits is 92543