এই সমস্যায়, আমাদের একটি এলিমেন্ট N দেওয়া আছে। আমাদের কাজ হল নেক্সট প্যালিনড্রোম প্রাইম খুঁজে বের করা।
সমস্যা বর্ণনা - আমাদের এমন সবচেয়ে ছোট প্রাইম নম্বর বের করতে হবে যা প্যালিনড্রোম সংখ্যাও হয় এবং N-এর চেয়ে বড়।
প্যালিনড্রোম নম্বর হল এমন সংখ্যা যেটি উল্টে পড়লেও একই থাকে।
প্রাইম নম্বর হল এমন সংখ্যা যেটির ফ্যাক্টর শুধু ১ এবং সেটি নিজে।
উদাহরণ
ইনপুট
N = 12
আউটপুট
101
ব্যাখ্যা
১২-এর চেয়ে বড় প্যালিনড্রোম সিরিজ: ২২, ৩৩, ৪৪, ৫৫, ৬৬, ৭৭, ৮৮, ৯৯, ১০১… এদের মধ্যে সবচেয়ে ছোট প্রাইম প্যালিনড্রোম হল ১০১।
সমাধানের পদ্ধতি
এই সমস্যার সহজ সমাধান হল N-এর চেয়ে বড় সব প্যালিনড্রোম বের করা যা প্রাইম।
একটি আরও দক্ষ সমাধান হল ইভেন ডিজিট প্যালিনড্রোম ১১-এর গুণফল হয় বলে চেনা।
প্রমাণ:
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);
string 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 " << primePalindrome(N);
return 0;
}
আউটপুট
The next prime palindrome is 433
দ্রষ্টব্য: মূল কোডের আউটপুটটি ভুল প্রিন্ট করা হয়েছিল (next number with same set of digits)। সঠিক আউটপুট ৪৩৩ হওয়া উচিত।
