C言語で指定された数のすべての素因数を効率的に求めるプログラム

この記事では、ある整数のすべての素因数を効率的に求めて出力する方法を解説します。例として、n = 1092 という数を考えてみましょう。1092 の素因数は 2、2、3、7、13 です。この問題を効率よく解くためには、以下の手順に従います。

• 数が 2 で割り切れる間、「2」を出力し続け、そのたびに数を 2 で割っていきます。
• この処理が終わった時点で、残りの数は必ず奇数になります。そこで、3 からその数の平方根までの範囲で、現在の値（奇数のみ）で割り切れるかどうかを確認します。割り切れる場合は出力し、数をその値で割って処理を繰り返します。

より理解しやすいように、アルゴリズムを見てみましょう。

アルゴリズム

printPrimeFactors(n)

begin
    while n is divisible by 2, do
        print 2
        n := n / 2
    done
    for i := 3 to √n, increase i by 2, do
        while n is divisible by i, do
            print i
            n := n / i
        done
    done
    if n > 2, then
        print n
    end if
end

C言語による実装例

#include<stdio.h>
#include<math.h>

void primeFactors(int n) {
    int i;
    // 2で割り切れる間、2を出力してnを半分にしていく
    while(n % 2 == 0) {
        printf("%d, ", 2);
        n = n/2;
    }
    // 奇数のみを調べるため、iは2ずつ増やす
    for(i = 3; i <= sqrt(n); i=i+2){
        while(n % i == 0) {
            printf("%d, ", i);
            n = n/i;
        }
    }
    // 残ったnが2より大きければ、それ自体が素因数
    if(n > 2) {
        printf("%d, ", n);
    }
}

main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    primeFactors(n);
}

実行結果

Enter a number: 24024
2, 2, 2, 3, 7, 11, 13,

このアルゴリズムのポイント

この手法が効率的である理由は、試し割り法の範囲を平方根までに限定している点にあります。合成数 n の素因数は必ず √n 以下に少なくとも一つ存在するため、√n まで確認すれば十分です。また、2 を先に取り除いた後は奇数だけを調べることで、計算量をさらに約半分に削減できます。

計算量は最悪の場合でも O(√n) となり、単純に 1 から n まで全ての数を試す方法（O(n)）と比べて大幅に高速です。特に大きな数の素因数分解において、この違いは顕著に現れます。