C++でのメビウス関数のプログラム

与えられた数n;タスクは、数nのメビウス関数を見つけることです。

メビウス関数とは何ですか？

メビウス関数は、

$$ \ mu（n）\ equiv \ begin {cases} 0 \\ 1 \\（-1）^ {k} \ end {cases} $$

n =0nに1つまたは複数の繰り返し因子がある場合

n =1 n=1の場合

n =（-1）knが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

特定の問題を解決するために使用するアプローチ −

• 入力Nを取ります。
• iを1からN未満に反復し、Nの除算数を確認し、それが素数であるかどうかを確認します。
• 両方の条件が満たされる場合、数値の2乗も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