यह देखते हुए कि कार्य [1, N] की सीमा में हो सकता है, जहां N दिया गया है, अद्वितीय अभाज्य गुणनखंडों की अधिकतम संख्या ज्ञात करना है।
आइए अब समझते हैं कि हमें एक उदाहरण का उपयोग करके क्या करना है -
इनपुट -एन=100
आउटपुट -3
स्पष्टीकरण - आइए 30 को [1, 100]
. के दायरे में लें30 =3 * 2 * 5 =अद्वितीय अभाज्य गुणनखंड। इसलिए, [1, 100] की सीमा में अधिकतम 3 अद्वितीय कारक मिल सकते हैं।
इनपुट -एन=300
आउटपुट -4
निम्नलिखित कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है
-
फ़ंक्शन मैक्सप्राइम () में हम पहले जांच करेंगे कि क्या (एन <2)। यदि ऐसा है तो बस शून्य लौटाएं, अन्यथा आगे बढ़ें।
-
फिर हम दी गई संख्या N से पहले सभी अभाज्य संख्याओं का पता लगाने के लिए एराटोस्थनीज की छलनी का उपयोग करेंगे।
-
उत्पाद और अंतिम उत्तर को क्रमशः स्टोर करने के लिए int प्रकार के दो चर pro=1 और max=0 प्रारंभ करें।
-
एराटोस्थनीज की छलनी के अंदर हम अभाज्य संख्याओं के पहले सेट को तब तक गुणा करेंगे जब तक कि उत्पाद N से छोटा न रह जाए - pro=*p;
-
जांचें कि क्या (समर्थक> एन)। यदि ऐसा है तो अधिकतम लौटाएं और अधिकतम में 1 जोड़ें।
-
चलनी के बाहर, अधिकतम भी लौटाएं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int MaxPrime(int N){
if (N < 2)
return 0;
// Using Sieve of Eratosthenes
bool Arr[N+1];
memset(Arr, true, sizeof(Arr));
int pro = 1, max = 0;
for (int p=2; p*p<=N; p++){
if (Arr[p] == true){
for (int i=p*2; i<=N; i += p)
Arr[i] = false;
/*Multiply first set of prime numbers while product remains smaller than N*/
pro *= p;
if (pro > N)
return max;
max++;
}
}
return max;
}
//Main function
int main(){
int N = 300;
cout << MaxPrime(N);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो हमें निम्न आउटपुट मिलेगा -
4