C++ 뫼비우스 함수 프로그램

주어진 숫자 n; 작업은 숫자 n의 뫼비우스 함수를 찾는 것입니다.

뫼비우스 기능이란?

뫼비우스 함수는 다음과 같이 정의되는 정수론 함수입니다.

$$\mu(n)\equiv\begin{케이스}0\\1\\(-1)^{k}\end{케이스}$$

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

주어진 문제를 해결하기 위해 사용할 접근 방식 -

• N을 입력합니다.
• 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