C++로 구현하는 뫼비우스(Möbius) 함수 프로그램

주어진 자연수 n에 대해 해당 수의 뫼비우스 함수(Möbius Function) 값을 구하는 것이 이번 글의 목표입니다. 뫼비우스 함수는 정수론에서 중요하게 활용되는 함수로, 소인수 분해와 밀접한 관련이 있습니다.

뫼비우스 함수란 무엇인가?

뫼비우스 함수는 정수론에서 다루어지는 함수로, 일반적으로 μ(n)으로 표기하며 다음과 같이 정의됩니다.

μ(n) = 0 : n이 하나 이상의 거듭 제곱 형태로 반복되는 소인수를 가질 때
μ(n) = 1 : n = 1일 때
μ(n) = (-1)^k : n이 서로 다른 k개의 소수(prime number)들의 곱일 때

쉽게 말해, 어떤 수를 소인수분해했을 때 같은 소수가 두 번 이상 등장하면 0, 모든 소인수가 한 번씩만 등장한다면 소인수의 개수가 홀수면 -1, 짝수면 1을 반환하는 함수입니다.

예제

입력: N = 17
출력: -1
설명: 소인수는 17 하나뿐이므로 k = 1,
(-1)^k = (-1)^1 = -1

입력: N = 6
출력: 1
설명: 소인수는 2와 3이므로 k = 2,
(-1)^k = (-1)^2 = 1

입력: N = 25
출력: 0
설명: 소인수 5가 두 번(5²) 등장하므로 답은 0

문제 해결 접근 방법

이 문제는 다음과 같은 단계로 해결할 수 있습니다.

정수 N을 입력받습니다.
i를 1부터 N까지 반복하면서, i가 N의 약수인지 동시에 i가 소수인지 검사합니다.
두 조건을 모두 만족할 때, i² 역시 N을 나누어떨어뜨린다면 즉시 0을 반환합니다.
그렇지 않으면 소인수 개수 카운트(p)를 1 증가시킵니다.
모든 반복이 끝난 후, p가 홀수면 -1을, 짝수면 1을 반환합니다.
최종 결과를 출력합니다.

알고리즘

시작
Step 1 → 함수 bool isPrime(int n)
    변수 i 선언
    만약 n < 2라면,
        false 반환
    i = 2부터 i * i <= n까지 반복:
        만약 n % i == 0이라면
            false 반환
        종료
        true 반환
Step 2 → 함수 int mobius(int N)
    변수 i와 p = 0 선언
    만약 N == 1이라면,
        1 반환
    종료
    i = 1부터 i <= N까지 반복:
        만약 N % i == 0 이고 isPrime(i)라면
            만약 N % (i * i) == 0이라면
                0 반환
            아니면
                p를 1 증가
            종료
        종료
    (p % 2 != 0)이면 -1, 아니면 1 반환
Step 3 → 함수 int main()
    변수 N을 선언하고 17로 설정
    mobius(N)의 결과를 출력
종료

C++ 전체 코드

#include<iostream>
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

N = 17을 입력했을 때, 17은 소수이며 소인수가 하나(k = 1)뿐이므로 (-1)¹ = -1이 출력됩니다.

성능 개선 팁

위 구현은 1부터 N까지 모든 수를 순회하며 매번 소수 여부를 검사하므로 시간 복잡도가 대략 O(N√N)으로 비교적 느립니다. 실무에서는 2부터 √N까지만 나누어 보며 소인수를 추출하는 방식(O(√N))을 사용하면 훨씬 효율적으로 뫼비우스 함수 값을 계산할 수 있습니다. 또한 에라토스테네스의 체를 활용하면 여러 수에 대한 뫼비우스 값을 한꺼번에 빠르게 전처리할 수 있습니다.