इस लेख में, हम 1 से n (दिया गया) तक की उन संख्याओं को खोजने की समस्या पर चर्चा करेंगे जो 2 से 10 तक किसी भी संख्या से विभाजित नहीं हो सकतीं। आइए इसे कुछ उदाहरणों से समझते हैं:
इनपुट: num = 14 आउटपुट: 3 व्याख्या: तीन संख्याएं हैं, 1, 11, और 13, जो विभाज्य नहीं हैं। इनपुट: num = 21 आउटपुट: 5 व्याख्या: पांच संख्याएं हैं 1, 11, 13, 17, और 19, जो विभाज्य नहीं हैं।
समाधान का दृष्टिकोण
सरल दृष्टिकोण
यदि हम 1 से num तक हर संख्या की जांच करते हैं कि क्या यह 2 से 10 तक किसी भी संख्या से विभाजित हो सकती है। यदि नहीं, तो काउंट बढ़ाएं। लेकिन इस दृष्टिकोण में बहुत अधिक समय लगेगा जिससे समय जटिलता बढ़ जाएगी।
कुशल दृष्टिकोण
हम जो सबसे अच्छा दृष्टिकोण सोच सकते हैं वह है पहले 1 से num तक की उन संख्याओं को खोजना जो रेंज [2, 10] में किसी भी संख्या से विभाज्य हैं, फिर इस काउंट को num से घटाना।
तो पहले, हमें 2, 3, 4, 5, 10 से विभाज्य सभी संख्याओं को खोजने की आवश्यकता है। लेकिन 4, 6, 8, और 10 से विभाज्य संख्याएं 2 से विभाज्य हैं, और 3 से विभाज्य संख्याएं 6 और 9 से विभाज्य हैं।
हमें 2, 3, 5, और 7 से विभाज्य सभी संख्याओं को खोजने की आवश्यकता है। और इसकी गणना हम समावेश-बहिष्करण सिद्धांत से कर सकते हैं।
समावेश-बहिष्करण सिद्धांत
यह बताता है कि हमें प्रत्येक एकल सेट के आकार को शामिल करना चाहिए, आपको जोड़ीदार प्रतिच्छेदन के आकार को हटाना चाहिए, तीन सेटों के प्रतिच्छेदन के आकार को जोड़ना चाहिए, और इसी तरह।
सभी संख्याओं को खोजने का सूत्र है,
= NUM - X + Y - Z + A।
जहां,
X = 2, 3, 5, 7 से विभाज्य संख्या ([num/2] + [num/3] + [num/5] + [num/7]) Y = (2,3), (2,5), (2,7), (3,5), (3,5), (3,7) और (5,7) से विभाज्य संख्या = ([num/(2*3)] + [num/(2*5)] + [num/(2*7)] + [num/(3*5)] + num/(3*7)] + [num/(5*7)]) Z = (2,3,5), (2,3,7), (2,5,7) और (3,5,7) से विभाज्य संख्या = ([num/(2*3*5)] + [num/(2*3*7)] + [num/(2*5*7)] + [num/(3*5*7)]) A = (2,3,5,7) से विभाज्य संख्या = ([num/(2*3*5*7)])
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 21, result;
// समावेश-बहिष्करण सिद्धांत से सूत्र लागू करना
// 2 से 10 तक किसी भी संख्या से विभाज्य न होने वाली संख्याओं की गिनती खोजने के लिए।
result = n - n/2 - n/3 - n/5 - n/7
+ n/6 + n/10 + n/14 + n/15 + n/21 + n/35
- n/30 - n/42 - n/70 - n/105 + n/210;
cout << "गिनती, जो [2, 10] से विभाज्य नहीं है: " << result;
return 0;
}
आउटपुट
गिनती, जो [2, 10] से विभाज्य नहीं है: 5
निष्कर्ष
इस लेख में, हम 2 से n तक गैर-विभाज्य संख्याओं को खोजने के तरीके पर चर्चा करते हैं। इस समस्या को हल करने के लिए, हमने समावेश-बहिष्करण सिद्धांत पर चर्चा की। हमने O(1) जटिलता के साथ परिणाम प्राप्त करने के लिए दृष्टिकोण लागू करने के लिए C++ प्रोग्राम पर भी चर्चा की। आप इस प्रोग्राम को Java, C, Python आदि किसी भी अन्य भाषा में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।