C言語で数の最大の素因数を求めるプログラム

素因数とは

素因数（そいんすう）とは、ある正の整数を余りなく割り切ることができる素数のことです。これらの数を見つける作業は「整数の因数分解」または「素因数分解」と呼ばれます。

例：288 の素因数は次のとおりです。
288 = 2 × 2 × 2 × 2 × 2 × 3 × 3

入力：n = 124
出力：31 が最大の素因数です！

アルゴリズムの考え方

まず、対象となる数のすべての素因数を求め、その中で最も大きいものを出力します。たとえば 124 を素因数分解すると、124 = 2 × 2 × 31 となり、この中で最大の素因数は 31 です。

具体的な手順は以下のとおりです。

• 2 から順に割る数（div）を用意し、n を割り切れるかどうかを判定します。
• 割り切れない場合は div を 1 ずつ増やします。
• 割り切れた場合は、そのときの n を最大の素因数候補（maxFact）として記録し、n を div で割ります。
• n が 1 になった時点で、記録しておいた値が最大の素因数となるため、結果を出力して処理を終了します。

C言語による実装例

#include <stdio.h>
int main() {
    long int n;
    n = 3453;
    long int div = 2, ans = 0, maxFact;
    while(n != 0) {
        if(n % div != 0)
            div = div + 1;
        else {
            maxFact = n;
            n = n / div;
            if(n == 1) {
                printf("%d is the largest prime factor !", maxFact);
                ans = 1;
                break;
            }
        }
    }
    return 0;
}

実行結果

1151 is the largest prime factor !

この例では 3453 = 3 × 1151 と素因数分解できるため、最大の素因数である 1151 が出力されます。このアルゴリズムは小さい素数から順に割っていくことで、最後に残った商が必ず最大の素因数になるという性質を利用しています。