C++ . का उपयोग करके उन संख्याओं को ज्ञात कीजिए जो [2, 10] की श्रेणी में किसी भी संख्या से विभाज्य नहीं हैं

इस लेख में, हम 1 से n(दिए गए) तक की संख्याओं को खोजने की समस्या पर चर्चा करेंगे, जिन्हें 2 से 10 तक किसी भी संख्या से विभाजित नहीं किया जा सकता है। आइए इसे कुछ उदाहरणों से समझते हैं -

Input : num = 14
Output : 3
Explanation: There are three numbers, 1, 11, and 13, which are not divisible.

Input : num = 21
Output : 5
Explanation: There are five numbers 1, 11, 13, 17, and 19, which are not divisible.

समाधान खोजने के लिए दृष्टिकोण

सरल तरीका

यदि हम 1 से अंक तक की प्रत्येक संख्या की जाँच करें, क्या इसे 2 से 10 तक किसी भी संख्या से विभाजित किया जा सकता है। यदि नहीं, तो गिनती बढ़ाएँ। लेकिन इस दृष्टिकोण में बहुत अधिक समय लगेगा इसलिए समय जटिलता बढ़ रही है।

कुशल दृष्टिकोण

सबसे अच्छा तरीका जो हम सोच सकते हैं, वह यह है कि पहले 1 से अंक तक की संख्याओं को [2, 10] के दायरे में किसी भी संख्या से विभाजित किया जाए, फिर इस संख्या को संख्या से घटाएं।

तो सबसे पहले, हमें 2, 3, 4, 5,10 से विभाज्य सभी संख्याएँ ज्ञात करनी होंगी। लेकिन 4, 6, 8 और 10 से विभाज्य संख्याएँ 2 से विभाज्य होती हैं, और तीन से विभाज्य संख्याएँ 6 और 9 से विभाज्य होती हैं।

हमें 2, 3, 5, और 7 से विभाज्य सभी संख्याएँ ज्ञात करनी होंगी और इसकी गणना हम समावेश-बहिष्करण सिद्धांत से कर सकते हैं।

समावेश-बहिष्करण सिद्धांत

इसमें कहा गया है कि हमें हर एक सेट के आकार को शामिल करना चाहिए, आपको जोड़ीवार चौराहे के आकार को हटा देना चाहिए, सभी चौराहे के तीन सेटों के आकार को जोड़ा जाना चाहिए, और इसी तरह।

सभी संख्याएँ ज्ञात करने का सूत्र है,

= NUM – X + Y – Z + A.

कहां,

X = num divisible by 2, 3, 5, 7 ( [num / 2] + [num / 3] + [num / 5] + [num / 7] )

Y = num divisible by (2,3), (2, 5), (2, 7), (3, 5), (3, 5), (3, 7) and (5, 7) = ( [num / (2 * 3)] + [num / (2 * 5)] + [num / (2 * 7)] + [num / (3 * 5)] + num / (3 * 7)] + [num / (5 * 7)] ).

Z = num divisible by (2, 3, 5), (2, 3, 7), (2, 5, 7) and (3, 5, 7) = ( [num / (2 * 3 * 5)] + [num / (2 * 3 * 7)] + [num / (2 * 5 * 7)] + [num / (3 * 5 * 7)] )

A = num divisible by (2, 3, 5, 7) = ( [num / (2 * 3 * 5 * 7)] )

उदाहरण

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n = 21, result;
   // applying formula from inclusion - exclusion principle
   // to find the count of numbers not divisible by any number from 2 to 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 << "The count of numbers, not div by [2, 10] is: " << result;

   return 0;
}

आउटपुट

The count of numbers, not div by [2, 10] is: 5

निष्कर्ष

इस लेख में, हमने 2 से n तक की अभाज्य संख्याओं को ज्ञात करने के तरीके पर चर्चा की। इस समस्या को हल करने के लिए, हमने समावेश-बहिष्करण सिद्धांत पर चर्चा की। हमने ओ (1) जटिलता के साथ परिणाम प्राप्त करने के लिए दृष्टिकोण लागू करने के लिए सी ++ प्रोग्राम पर भी चर्चा की। आप इस प्रोग्राम को किसी अन्य भाषा जैसे जावा, सी, पायथन, आदि में लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख मददगार लगा होगा।