এই সমস্যায়, আমাদের একটি সংখ্যা n দেওয়া আছে। আমাদের কাজ হল এমন সর্বোচ্চ সংখ্যক প্রাইম সংখ্যা বের করা যাদের যোগফল দেওয়া N-এর সমান।
এখানে, আমরা সর্বোচ্চ কতগুলো প্রাইম সংখ্যা যোগ করে দিলে যোগফল সংখ্যাটির সমান হবে তা বের করব।
প্রাইম সংখ্যা হলো যেসব সংখ্যা শুধু নিজস্বে এবং ১ দ্বারা বিভাজ্য।
একটি উদাহরণ নিয়ে সমস্যাটি বুঝতে চাই −
ইনপুট − N = 9
আউটপুট − 4
ব্যাখ্যা −
৯ কে প্রাইম সংখ্যাগুলোর যোগফল হিসেবে নিচের উপায়ে প্রকাশ করা যায়: 2, 2, 2, 3 3, 3, 3 2, 2, 5 2, 7 এই সব থেকে সর্বোচ্চ ৪টি প্রাইম সংখ্যা ব্যবহার করা হয়েছে।
সর্বোচ্চ প্রাইম সংখ্যা ব্যবহার করা যাবে তা নির্ভর করে করায় কতগুলো সবচেয়ে ছোট প্রাইম সংখ্যা যোগ করে যোগফল করা যায়।
সबচে ছোট প্রাইম সংখ্যা হল ২। এবং এর পরে বড় প্রাইম সংখ্যা হল ৩, যা বিজোড়।
তাই, কাউন্ট সর্বোচ্চ হবে যদি আমরা শুধু ২ এবং ৩ ব্যবহার করে যোগফল বের করি। এর ভিত্তিতে আমরা সমস্যাটিকে দুটি কেসে ভাগ করতে পারি −
কেস ১ − যদি N জোড় হয়, যোগফলে সব প্রাইম সংখ্যা ২ হবে। তাই কাউন্ট হবে n/2।
কেস ২ − যদি N বিজোড় হয়, যোগফলে সব প্রাইম সংখ্যা ২ হবে ছাড়া একটি যা হবে ৩। তাই কাউন্ট হবে (n-1/2)।
উদাহরণ
C++-এ দেওয়া N-এর সমান যোগফল দেয় এমন সর্বোচ্চ প্রাইম সংখ্যা বের করার প্রোগ্রাম
#include <iostream> using namespace std; int maxPrimeCount(int n){ // বিজোড় কেসের জন্য রেজাল্ট হবে (n-1)/2 একই return n / 2; } int main(){ int n = 9; cout<<"The maximum number of primes whose sum is equal to "<<n<<" is "<<maxPrimeCount(n); return 0; }
আউটপুট
The maximum number of primes whose sum is equal to 9 is 4
