दो संख्याओं को प्रारंभ और अंत में दिया गया है जो सकारात्मक पूर्णांकों की श्रेणी का प्रतिनिधित्व करते हैं। लक्ष्य उन सभी संख्याओं की गिनती का पता लगाना है जो सीमा में हैं [प्रारंभ, अंत] और अभाज्य गुणनखंड इस प्रकार हैं कि उस संख्या के सभी अभाज्य गुणनखंडों में ऐसी शक्तियाँ हों कि उनके पास GCD 1 के रूप में हो।
यदि किसी संख्या का अभाज्य गुणनखंड 2 p . है * 3 q * 5 r ….. तब घात p,q,r ... में gcd=1 होना चाहिए।
आइए उदाहरणों से समझते हैं।
उदाहरण के लिए
इनपुट - प्रारंभ =1, अंत =10
आउटपुट - 1 के बराबर अभाज्य गुणनखंडों की शक्तियों की GCD वाली श्रेणी में संख्याओं की संख्या हैं:6
स्पष्टीकरण - नंबर हैं:
2 (2 1 ), 3 ( 3 1 ), 5 ( 5 1 ), 7 (7 1 ), 8 ( 2 3 ) और 10 ( 2 1 *5 1 ) प्रत्येक अभाज्य गुणनखंड की सभी शक्तियों में gcd 1 होता है।
इनपुट - प्रारंभ =11, अंत =20
आउटपुट - 1 के बराबर अभाज्य गुणनखंडों की शक्तियों की GCD वाली श्रेणी में संख्याओं की संख्या हैं:9
स्पष्टीकरण - नंबर हैं:
11 ( 11 1 ), 12 ( 3 1 *2 2 ), 13 ( 13 1 ), 14 ( 2 1 *7 1 ), 15 ( 3 1 *5 1 ), 17 ( 17 1 ), 18 ( 2 1 *3 2 ), 19 ( 19 1 ) और 20 ( 2 2 *5 1 ) प्रत्येक अभाज्य गुणनखंड की सभी शक्तियों में gcd 1 होता है।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम शुरू से अंत तक की सभी संख्याओं की गणना करेंगे जो पूर्ण शक्तियाँ नहीं हैं। चूंकि गैर-पूर्ण शक्तियां उपरोक्त शर्त को पूरा करेंगी। इसके लिए हम सभी सिद्ध शक्तियों को खोज लेंगे और उन्हें कुल संख्या से हटा देंगे।
उत्तर होगा =प्रारंभ-अंत +1 - (श्रेणी में संख्याओं की गणना [प्रारंभ, अंत] जो पूर्ण शक्तियां हैं)।
- श्रेणी चर को इनपुट के रूप में प्रारंभ और अंत लें।
- 3 से अधिक पावर स्टोर करने के लिए वेक्टर vec लें।
- पूर्ण वर्ग वाली संख्याओं को संग्रहीत करने के लिए एक सेट सेट लें।
- पूर्ण वर्ग न होने वाली संख्याओं को संग्रहीत करने के लिए एक सेट सेट_2 लें।
- फ़ंक्शन कैलकुलेट () वेक्टर vec को पॉप्युलेट करता है और सेट करता है और सेट करता है_2। पूर्ण वर्ग, गैर पूर्ण वर्ग और घात>3. . वाली संख्याओं को अलग करने के लिए
- ट्रैवर्स लूप के लिए i=2 से i<आकार तक का उपयोग करते हैं।
- सेट करने के लिए सही शक्तियां i*i डालें।
- अगर sett.find(i) !=sett.end()) सही है तो i एक पूर्ण वर्ग है और सेट में मौजूद है इसलिए कुछ न करें।
- लूप के दौरान तब तक चलाएं जब तक कि वर्तमान संख्या की शक्ति बड़ी से कम न रहे।
- सेट-2 में विषम घात डालें क्योंकि सम घातें पूर्ण वर्ग और सेट में होती हैं।
- अंत में लूप के लिए उपयोग करके वेक्टर vec में sett_2 के सॉर्ट किए गए मान डालें।
- फ़ंक्शन GCD_1(लॉन्ग इंट स्टार्ट, लॉन्ग इंट एंड) इनपुट के रूप में रेंज लेता है और 1 के बराबर प्राइम फ़ैक्टर्स की शक्तियों की GCD वाली रेंज में नंबरों की गिनती लौटाता है।
- कॉल कैलकुलेट ()।
- per_sq =floor(sqrtl(end)) - floor(sqrtl(start - 1)). के अनुसार श्रेणी में पूर्ण वर्गों की गणना करें।
- ऊपरी_बाउंड(vec.begin(), vec.end(), end) - vec.begin() का उपयोग करके vec में प्रारंभ के ऊपरी मान की गणना करें।
- इसी तरह नीचे का उपयोग करके vec में अंत का निचला मान =निचला_बाउंड(vec.begin(), vec.end(), start) - vec.begin()।
- per_pow =per_sq + (ऊपर - नीचे) के रूप में पूर्ण शक्तियों की गणना करें।
- उत्तर होगा काउंट =(अंत - प्रारंभ + 1) - per_pow.
- अंत में परिणाम के रूप में वापसी की गणना।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define size 1000005
#define large 1e18
vector < long int > vec;
set < long int > sett;
set < long int > sett_2;
void calculate() {
for (long int i = 2; i < size; i++) {
sett.insert(i * i);
if (sett.find(i) != sett.end()) {
continue;
}
long int total = i;
while (i * i <= large / total) {
total *= (i * i);
sett_2.insert(total);
}
}
for (auto it: sett_2) {
vec.push_back(it);
}
}
long int GCD_1(long int start, long int end) {
calculate();
long int per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1));
long int top = upper_bound(vec.begin(), vec.end(), end) - vec.begin();
long int bottom = lower_bound(vec.begin(), vec.end(), start) - vec.begin();
long int per_pow = per_sq + (top - bottom);
long int count = (end - start + 1) - per_pow;
return count;
}
int main() {
long int start = 10, end = 40;
cout << "Count of numbers in a range having GCD of powers of prime factors equal to 1 are: " << GCD_1(start, end);
return 0;
} यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
आउटपुट
Count of numbers in a range having GCD of powers of prime factors equal to 1 are: 7