C++ में मोबियस फंक्शन के लिए प्रोग्राम

एक संख्या n दी गई है; कार्य संख्या n का मोबियस फंक्शन ढूंढना है।

मोबियस फंक्शन क्या है?

मोबियस फंक्शन एक संख्या सिद्धांत फंक्शन है जिसे परिभाषित किया गया है:

μ(n) = 0 यदि n में एक या एक से अधिक दोहराए गए फैक्टर हैं

μ(n) = 1 यदि n = 1

μ(n) = (-1)ᵏ यदि n, k विशिष्ट अभाज्य संख्याओं का गुणनफल है

उदाहरण

इनपुट: N = 17
आउटपुट: -1
व्याख्या: अभाज्य फैक्टर: 17, k = 1, (-1)ᵏ → (-1)¹ = -1

इनपुट: N = 6
आउटपुट: 1
व्याख्या: अभाज्य फैक्टर: 2 और 3, k = 2, (-1)ᵏ → (-1)² = 1

इनपुट: N = 25
आउटपुट: 0
व्याख्या: अभाज्य फैक्टर 5 है जो दो बार आता है इसलिए उत्तर 0 है

दिए गए समस्या को हल करने के लिए हम जिस दृष्टिकोण का उपयोग करेंगे -

• एक इनपुट N लें।
• 1 से N से कम तक i को इटरेट करें, N की विभाज्य संख्या की जांच करें और जांचें कि क्या यह अभाज्य है या नहीं।
• यदि दोनों शर्तें पूरी होती हैं तो हम जांचेंगे कि क्या उस संख्या का वर्ग भी N को विभाजित करता है तो 0 वापस करें।
• अन्यथा हम अभाज्य फैक्टर की गिनती बढ़ाएंगे, यदि गिनती सम है तो 1 वापस करें अन्यथा यदि यह विषम है तो -1 वापस करें।
• परिणाम प्रिंट करें।

एल्गोरिदम

शुरुआत
चरण 1 → फंक्शन bool isPrime(int n) में
   i घोषित करें
   यदि n < 2 तो,
      false वापस करें
   लूप i = 2 और i * i <= n और i++ के लिए
      यदि n % i == 0
        false वापस करें
      true वापस करें

चरण 2 → फंक्शन int mobius(int N) में
   i और p = 0 घोषित करें
   यदि N == 1 तो,
      1 वापस करें
   लूप i = 1 और i <= N और i++ के लिए
      यदि N % i == 0 && isPrime(i)
        यदि (N % (i * i) == 0)
          0 वापस करें
        अन्यथा
          p को 1 से बढ़ाएं
        अंत
      अंत
   (p % 2 != 0) ? -1 : 1 वापस करें

चरण 3 → फंक्शन int main() में
   N = 17 घोषित और सेट करें
   mobius(N) से परिणाम प्रिंट करें
रोकें

उदाहरण

#include 
using namespace std;

// फंक्शन जांचने के लिए कि n अभाज्य है या नहीं
bool isPrime(int n) {
    int i;
    if (n < 2)
        return false;
    for (i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}

int mobius(int N) {
    int i;
    int p = 0;
    // यदि n 1 है
    if (N == 1)
        return 1;
    // एक अभाज्य फैक्टर i के लिए जांचें कि क्या i² भी एक फैक्टर है।
    for (i = 1; i <= N; i++) {
        if (N % i == 0 && isPrime(i)) {
            // जांचें कि क्या N, i² से विभाज्य है
            if (N % (i * i) == 0)
                return 0;
            else
                // i केवल एक बार आता है, p बढ़ाएं
                p++;
        }
    }
    // सभी अभाज्य फैक्टर केवल एक बार मौजूद हैं
    // यदि p सम है तो 1 वापस करें अन्यथा -1
    return (p % 2 != 0) ? -1 : 1;
}

// ड्राइवर कोड
int main() {
    int N = 17;
    cout << mobius(N) << endl;
}

आउटपुट

-1