এই সমস্যায়, আমাদের একটি বিজোড় সংখ্যা N দেওয়া হয়েছে। আমাদের কাজ হলো বিজোড় সংখ্যক প্রাইম নম্বরের যোগফল হিসেবে প্রকাশ করা।
সংখ্যাটি প্রকাশ করার সময় সর্বোচ্চ তিনটি প্রাইম নম্বর থাকতে পারে।
উদাহরণ দিয়ে সমস্যাটি বোঝা যাক
ইনপুট: N = 55
আউটপুট: 53 + 2
সমাধানের পদ্ধতি
বিজোড় সংখ্যাটি প্রাইমের যোগফল হিসেবে প্রকাশ করা যায়। এই প্রাইমগুলো বিবেচনা করলে তিনটি কেস থাকে।
কেস ১: যদি n প্রাইম হয়, তবে এটি একটা প্রাইম নম্বর n হিসেবে প্রকাশ করা যায়।
কেস ২: যদি (n - 2) প্রাইম হয়, তবে এটি দুটি প্রাইম নম্বরের যোগফল হিসেবে প্রকাশ করা যায় n-2 এবং 2।
কেস ৩: (n - 3) হলো একটি জোড় সংখ্যা যা দুটি প্রাইম নম্বরের যোগফল হিসেবে প্রকাশ করা যায় গোল্ডব্যাকের অনুমান (Goldbach's conjecture) মেথড ব্যবহার করে যেখানে আমরা চেক করব একটি সংখ্যা A প্রাইম কিনা এবং {(n-3) - A} ও প্রাইম কিনা তারপর প্রিন্ট করব।
সমাধানটি ব্যাখ্যা করে প্রোগ্রাম
#include <iostream>
using namespace std;
bool isPrime(int x) {
if (x == 0 || x == 1)
return false;
for (int i = 2; i * i <= x; ++i)
if (x % i == 0)
return false;
return true;
}
void primeAsSumofPrime(int n) {
if (isPrime(n))
cout << n;
else if (isPrime(n - 2))
cout << "2 " << "+ " << (n - 2);
else {
cout << "3 " << "+ ";
n -= 3;
for (int i = 0; i < n; i++) {
if (isPrime(i) && isPrime(n - i)) {
cout << i << " + " << (n - i);
break;
}
}
}
}
int main() {
int n = 561;
cout << "The number " << n << " expressed as sum of primes is ";
primeAsSumofPrime(n);
return 0;
}
আউটপুট
The number 561 expressed as sum of primes is 3 + 11 + 547
