C++で実装するメビウス関数（μ関数）の求め方とサンプルコード

整数 n が与えられたとき、その数に対するメビウス関数（Möbius function）の値を求めるのが本記事の目的です。

メビウス関数とは？

メビウス関数は数論における重要な関数の一つで、μ(n) として表され、次のように定義されます。

• μ(n) = 0 … n が1つ以上の「繰り返し素因数」（同じ素因数を2回以上含む）を持つ場合
• μ(n) = 1 … n = 1 の場合
• μ(n) = (-1)^k … n が k 個の異なる素数の積で構成される場合

具体例

入力：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 ですが、2回現れるため答えは 0

解決のためのアプローチ

この問題は以下の手順で解くことができます。

1. 整数 N を入力として受け取ります。
2. i を 1 から N 未満まで順に走査し、N を割り切るかどうか、また i が素数かどうかを判定します。
3. 両方の条件を満たす場合、さらに i の2乗（i²）も N を割り切れるか確認します。割り切れれば 0 を返します。
4. そうでなければ素因数の個数カウント p を増やし、最終的に p が偶数なら 1、奇数なら -1 を返します。
5. 結果を出力します。

アルゴリズム

開始
ステップ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) の結果を出力
終了

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^2 も約数になるかを確認
    for (i = 1; i <= N; i++) {
        if (N % i == 0 && isPrime(i)) {
            // N が i^2 で割り切れるかチェック
            if (N % (i * i) == 0)
                return 0;
            else
                // i が1度だけ現れる場合、p をインクリメント
                p++;
        }
    }
    // すべての素因数が重複なく含まれている場合
    // p が偶数なら 1、奇数なら -1 を返す
    return (p % 2 != 0) ? -1 : 1;
}

// 実行コード
int main() {
    int N = 17;
    cout << mobius(N) << endl;
}

補足：計算量の改善ポイント

上記の実装では i を 1 から N まで全て調べているため、計算量は O(N√N) 程度になります。より効率的にしたい場合は、素因数分解を √N までの範囲で行う方法や、エラトステネスの篩を使って事前に素数リストを作成しておく方法が有効です。これにより大規模な入力でも高速にメビウス関数の値を求められます。

出力結果

-1

N = 17 の場合、素因数は 17 のみ（k = 1）なので、(-1)^1 = -1 が出力されます。このようにメビウス関数は、素因数の構成を見るだけで簡単に値を判定できる便利な数論関数です。