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

この記事では、ある整数の最大の素因数を効率的に求める方法を解説します。例として n = 1092 を考えてみましょう。1092 を素因数分解すると 2 × 2 × 3 × 7 × 13 となるため、最大の素因数は 13 です。

この問題を解くには、以下の手順に従います。

• 数が 2 で割り切れる間、最大値として 2 を記録し、数を 2 で繰り返し割ります。

• この時点で数は必ず奇数になっています。そこで 3 から数の平方根までの範囲を調べ、現在の値 i で割り切れる場合は i を最大の素因数として記録し、数を i で割りながら処理を続けます。

• 最後に、残った数が 2 より大きい場合（1 ではない場合）、その数自体が最大の素因数となります。

処理の流れをより明確に把握するために、アルゴリズムを確認してみましょう。

アルゴリズム

getMaxPrimeFactors(n)

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

C言語による実装例

#include<stdio.h>
#include<math.h>
int getMaxPrimeFactor(int n) {
   int i, max = -1;
   while(n % 2 == 0) {
      max = 2;
      n = n/2; /*2で割ることでnを小さくしていく*/
   }
   for(i = 3; i <= sqrt(n); i=i+2){ /*iを2ずつ増やし、奇数のみを調べる*/
      while(n % i == 0) {
         max = i;
         n = n/i;
      }
   }
   if(n > 2) {
      max = n;
   }
   return max;
}
main() {
   int n;
   printf("Enter a number: ");
   scanf("%d", &n);
   printf("Max prime factor: %d", getMaxPrimeFactor(n));
}

実行結果

Enter a number: 24024
Max prime factor: 13

このアルゴリズムの計算量は O(√n) であり、1 から順にすべての数を試す単純な全探索よりもはるかに効率的です。平方根まで調べれば十分な理由は、それより大きな約数が存在しても、対応する小さな約数が必ずペアとして存在するためです。また、最初に 2 をすべて取り除くことで、以降のループを奇数のみに限定でき、処理速度がさらに向上します。