ในปัญหานี้ เราได้รับองค์ประกอบ N เราจำเป็นต้องหาพาลินโดรมไพรม์ตัวต่อไป
คำอธิบายปัญหา − เราจำเป็นต้องหาจำนวนเฉพาะที่น้อยที่สุดซึ่งเป็นจำนวนพาลินโดรมด้วย ซึ่งมากกว่า N
Palindrome Number คือตัวเลขที่ตัวเลขเหมือนกันทั้งสองทิศทาง
Prime Number คือตัวเลขหากตัวประกอบเป็น 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 ซึ่งทำให้เลขคู่ทั้งหมดไม่ใช่ palindrome
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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
