दिया गया कार्य [1, N] रेंज में एक संख्या में हो सकने वाले अधिकतम अद्वितीय अभाज्य गुणनखंडों की संख्या ढूंढना है जहां N दिया गया है।
उदाहरण से समझते हैं
इनपुट - N=100
आउटपुट - 3
व्याख्या - [1, 100] रेंज में 30 लेते हैं। 30 = 3 * 2 * 5 = अद्वितीय अभाज्य गुणनखंड। इसलिए, [1, 100] रेंज में अधिकतम 3 अद्वितीय गुणनखंड पाए जा सकते हैं।
इनपुट - N=300
आउटपुट - 4
प्रयुक्त दृष्टिकोण
MaxPrime() फंक्शन में हम पहले चेक करेंगे यदि (N < 2)। यदि हां तो बस शून्य वापस करें, अन्यथा आगे बढ़ें।
फिर हम एराटोस्थनीज की छलनी का उपयोग करके दी गई संख्या N से पहले की सभी अभाज्य संख्याएं ढूंढेंगे।
दो वेरिएबल pro=1 और max=0 को int टाइप का आरंभ करें गुणनफल और अंतिम उत्तर स्टोर करने के लिए क्रमशः।
एराटोस्थनीज की छलनी के अंदर हम अभाज्य संख्याओं के पहले सेट को तब तक गुणा करेंगे जब तक गुणनफल N से छोटा रहता है: pro *= p;
चेक करें यदि (pro > N)। यदि हां तो max वापस करें और max में 1 जोड़ें।
छलनी के बाहर, max भी वापस करें।
C++ प्रोग्राम उदाहरण
#include <bits/stdc++.h>
using namespace std;
int MaxPrime(int N) {
if (N < 2)
return 0;
// एराटोस्थनीज की छलनी का उपयोग
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;
/* अभाज्य संख्याओं के पहले सेट को तब तक गुणा करें जब तक गुणनफल N से छोटा रहे */
pro *= p;
if (pro > N)
return max;
max++;
}
}
return max;
}
int main() {
int N = 300;
cout << MaxPrime(N);
return 0;
}आउटपुट
4