Trong bài toán này, chúng ta được cung cấp một phần tử N. Chúng ta cần tìm số nguyên tố palindrome tiếp theo.
Mô tả sự cố - Ta cần tìm số nguyên tố nhỏ nhất cũng là số palindrome, lớn hơn N.
Số Palindrome là một số trong đó các số giống nhau ở cả hai hướng.
Số nguyên tố là một số nếu các thừa số duy nhất của nó là 1 và chính nó.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 12
Đầu ra
101
Giải thích
Chuỗi palindromes lớn hơn 12 là 22, 33, 44, 55, 66, 77, 88, 99,101… trong số này, palindrome nhỏ nhất là 101.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm tất cả các palindromes lớn hơnN là số nguyên tố.
Một giải pháp hiệu quả hơn là tìm chữ số chẵn palindrome là bội của 11.
Đây là bằng chứng về giải pháp này,
11% 11 = 0 1111% 11 = 0
Sử dụng điều này, chúng tôi sẽ tìm thấy palindrome với các chữ số chẵn -
xyzzyx% 11 =0, làm cho tất cả các chữ số chẵn không phải là palindrome.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The next number with same set of digits is 92543