इस समस्या में, हमें एक संख्या n दी गई है। हमारा कार्य उन अभाज्य संख्याओं की अधिकतम संख्या ज्ञात करना है जिनका योग दिए गए N के बराबर है।
यहां, हम अभाज्य संख्याओं की वह अधिकतम संख्या पाएंगे जो जोड़ने पर संख्या के बराबर होगी।
अभाज्य संख्याएँ वे संख्याएँ होती हैं जिन्हें स्वयं या एक से विभाजित किया जा सकता है।
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं -
इनपुट - एन =9
आउटपुट -4
स्पष्टीकरण -
9 can be repressed as the sum of prime numbers in the following ways: 2, 2, 2, 3 3, 3, 3 2, 2, 5 2, 7 Out of these the maximum number of primes used is 4.
उपयोग की जाने वाली अभाज्य संख्याओं की अधिकतम संख्या इस बात पर आधारित होगी कि योग बनाने के लिए कितनी छोटी अभाज्य संख्याओं को जोड़ा जा सकता है।
तो, सबसे छोटी अभाज्य संख्या 2 है। और क्रमागत बड़ी अभाज्य संख्या 3 है, जो विषम है।
इसलिए, यदि हम योग की गणना करते समय केवल 2 और 3 का उपयोग करते हैं, तो गिनती अधिकतम हो जाएगी। इसके आधार पर हम समस्या को दो स्थितियों में बाँट सकते हैं -
केस 1 - यदि N सम है, तो योग में सभी अभाज्य संख्याएँ 2 होंगी। तो, गिनती n/2 होगी।
केस 2 - यदि N विषम है, तो योग में सभी अभाज्य संख्याएँ 2 होंगी, केवल एक को छोड़कर जो कि 3 होगी। अतः, गणना (n-1/2) होगी।
उदाहरण
अधिकतम प्राइम खोजने के लिए प्रोग्राम जिसका योग C++ में दिए गए N के बराबर है
#include <iostream>
using namespace std;
int maxPrimeCount(int n){
//For odd case the result will same as (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