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

एक संख्या n दिया गया; कार्य संख्या n के मोबियस फ़ंक्शन को खोजना है।

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

मोबियस फ़ंक्शन संख्या सिद्धांत फ़ंक्शन है जिसे

$$\mu(n)\equiv\ start{cases}0\\1\\(-1)^{k}\end{cases}$$

n=0 यदि n में एक या एक से अधिक दोहराए गए कारक हैं

n=1 यदि n=1

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

उदाहरण

Input: N = 17
Output: -1
Explanation: Prime factors: 17, k = 1,
(-1)^k 🠠(-1)^1 = -1

Input: N = 6
Output: 1
Explanation: prime factors: 2 and 3, k = 2
(-1)^k 🠠(-1)^2 = 1

Input: N = 25
Output: 0
Explanation: Prime factor is 5 which occur twice so the answer is 0

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

• एक इनपुट एन लें।
• I को 1 से N से कम पर पुनरावृत्त करें, N की विभाज्य संख्या की जाँच करें और जाँचें कि यह अभाज्य है या नहीं।
• यदि दोनों शर्तें पूरी होती हैं तो हम जांच करेंगे कि क्या संख्या का वर्ग भी N को विभाजित करता है तो रिटर्न 0.
• अन्यथा हम अभाज्य गुणनखंडों की संख्या में वृद्धि करते हैं, यदि संख्या संख्या सम है तो विषम रिटर्न -1 होने पर 1 और लौटाएं।
• परिणाम प्रिंट करें।

एल्गोरिदम

Start
Step 1→ In function bool isPrime(int n)
   Declare i
   If n < 2 then,
      Return false
   Loop For  i = 2 and i * i <= n and i++
      If n % i == 0
         Return false    
      End If
      Return true
Step 2→ In function int mobius(int N)
   Declare i and p = 0
   If N == 1 then,  
      Return 1
   End if
   Loop For  i = 1 and i <= N and i++
      If N % i == 0 && isPrime(i)
         If (N % (i * i) == 0)
            Return 0
         Else
            Increment p by 1
         End if
      End if
   Return (p % 2 != 0)? -1 : 1
Step 3→ In function int main()
   Declare and set N = 17
   Print the results form mobius(N)
Stop

उदाहरण

#include<iostream>
using namespace std;
// Function to check if n is prime or not
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;
   //if n is 1
   if (N == 1)
   return 1;
   // For a prime factor i check if i^2 is also
   // a factor.
   for ( i = 1; i <= N; i++) {
      if (N % i == 0 && isPrime(i)) {
         // Check if N is divisible by i^2
         if (N % (i * i) == 0)
            return 0;
         else
            // i occurs only once, increase p
            p++;
      }
   }
   // All prime factors are contained only once
   // Return 1 if p is even else -1
   return (p % 2 != 0)? -1 : 1;
}
// Driver code
int main() {
   int N = 17;
   cout  << mobius(N) << endl;
}

आउटपुट

N = -1