【競プロ】素因数分解

🕒 2019/10/17 🔄 2023/05/01

ここでは、正の整数を素数だけの積で表す素因数分解について見ていきます。競プロ記事の一覧はこちら。

📘 目次

素因数分解

素数と合成数では、素数について見ました。素数とは、2以上の整数で、正の約数が1と自分だけのもののことをいいます。正の約数が2個、とも言い換えられます。

ある正の整数 $N$ が、ある素数 $p$ で割り切れる場合、この素数 $p$ のことを $N$ の素因数(prime factor) といいます。たとえば、 $12$ は $2$ でも割り切れるし、 $3$ でも割り切れるので、 $2$ も $3$ も $12$ の素因数です。 $5$ では割り切れないので、 $5$ は $12$ の素因数ではありません。 $4$ では割り切れますが素数ではないので、 $4$ は素因数ではありません。こういう場合は、因数といいます。

正の整数を素数だけの積で表すことを、素因数分解(prime factorization) といいます。例えば、 $12$ は、素数 $2$ を2回、 $3$ を1回掛けたものなので、\[ 12=2^2\times 3 \] と書けます（参考：整数の整数乗）。これが $12$ を素因数分解した結果です。

$5$ の素因数分解は $5$ です。素数の場合はそのままです。 $1$ の素因数分解は $1$ そのまま、とします。

今の時点では、このように分解して書いたところで何がいいのかわかりにくいですが、競プロでは（数学でも）、約数や公倍数を考える問題などで役に立ちます。

素因数分解を手で行う

それでは、実際に素因数分解をどうやって行うかを見てみましょう。足し算や掛け算のようにパッと答えが出るわけではなく、手順を踏んで計算する必要があります。ここでは、もっとも単純な方法を見ることにします。

$360$ を素因数分解してみます。まず、一番小さい素数 $2$ で割れるかを考えると、割り切れますね。割った結果は $180$ となります。もう一度 $2$ で割れるかを考えると、まだ割り切れます。合計で4回割り切れて、結果は $45$ となります。これ以上 $2$ では割り切れません。

次に小さい素数 $3$ で割り切れるかを考えると、2回割り切れることがわかります。割った結果は $5$ となります。これが素数なので、 $360$ の素因数分解は\[ 360=2^4\times 3^2\times 5 \]という形になります。

このように、2以上の整数 $N$ を素因数分解するには、小さい素数から順番に、割り切れるなら割り切れなくなるまで割る、割り切れなくなったら次の素数へ移動する、というのを繰り返していきます。こうすると、いつかは終わります。

一番計算回数が多くなる最悪なケースは $N$ が素数のときですが、これは素数と合成数で見たように、 $\sqrt{N}$ 以下の整数までをチェックするだけでOKです。これらで割り切れないなら、 $N$ が素数であることがわかります。合成数なら、 $\sqrt{N}$ 以下のどこかで割り切れます。

素因数分解を行うコード

先ほど見た内容を、C++のコードにしてみましょう。

丁寧にやるなら、まずは素数の一覧を作成すべきでしょう。しかし、実は少し横着ができて、次のように書けます。素因数を factors に入れていくことにします。2以上のint型の整数が入力される前提です。

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int main() {
  int N; cin >> N;
  vector<int> factors;

  for (int i = 2; i <= sqrt(N); i++) {
    while (N % i == 0) {
      factors.push_back(i);
      N /= i;
    }
    if (N == 1) break;
  }
  if (N != 1) factors.push_back(N);
  // cout << N << "\n";

  for (int i = 0; i < factors.size(); i++)
    cout << factors[i] << " ";

  return 0;
}

while文では、i で割れるだけ割っています。i が素数であるかどうかのチェックをしていないのですが、それは問題になりません。なぜなら、もし $10$ とか $21$ のような合成数で割る頃には、その手前にある小さな素数（2, 5, 3, 7 など）ですでに何度も割っているはずだからです。つまり、while文の内側が実行されるのは、i が素数のときしかありえません。

N を割っていき、1 になったら、それ以上チェックする必要はありません。そこで終了です。 N が 36 や 125 などの場合は、最終的に N == 1 となります。

一方、sqrt(N) までチェックした後に N != 1 となるケースもあります。その場合は、最終的には N が素数になっているということなので、最後に追加しています。このようになるケースは、 N が 5 や 11 というように初めから素数の場合もありますし、 12 や 360 や 35 のように、最後に一番大きな素因数が1つだけ残るときにも起こります。（コメント部分を解除して結果を確認してみましょう）

こうして、何回掛けられているかも含めて、素因数が factors に格納されます。ここでは、最後に表示しているだけですが、これを利用して、約数や公倍数などの問題を解いていくこともあります。

上のコードをそのまま使いまわせてしまいますが、 AOJ NTL_1_A Prime Factorizeができるでしょう。何も見ずにやってみましょう。

素因数分解の性質

素因数分解には、いくつかよい性質があります。

まず一つは、正の整数に対して、いつでも素因数分解ができる、という性質です。これはあまり不思議な感じはしないと思います。小さい素数から順番に試していけば、どんな正の整数に対しても素因数分解ができることは、上のコードを見ても想像できるでしょう。

もう一つの性質は、素因数分解は、掛け算の順序を無視すれば、一通りしかない、という性質です。これは少し不思議な感じがするかもしれません。

上のコードを見ると、小さい整数から順番に割り切れるかどうかを確かめていくため、素因数分解の仕方を1つは見つけることができます。しかし、他の表し方はないのでしょうか。たとえば、 $12$ は、ただの積に分解するだけなら $2\times 6$ とも $3\times 4$ とも表せるので一通りには決まりません。素因数分解でも、複数のあらわし方があっても不思議ではありません。

しかし、実際には一通りしかありません。たとえば、 $12$ はどのように分解しても、掛ける順番は違うかもしれませんが、 $2^2\times 3$ となる、という性質が知られています。この証明は少し難しいのでここでは取り上げませんが、この「（掛け算の順序を無視すれば）一通りしかない」という性質はとても強力な性質です。素因数分解での表し方が1つでも見つかれば、それが答えになることが保障されているからです。

素因数分解を式で表す

最後に、素因数分解を表した式を見ておきましょう。この数式は、問題文や解説文で出てくる可能性があります。初めて見ると文字が多くて目を伏せたくなりますが、意味するところが分かればそれほど怖くはありません。

2以上の整数 $N$ を素因数分解すると、いくつかの素数の積で書くことができます。ここで、出てくる素数の種類が $n$ 種類であったとします。 $N=360$ なら、素因数は $2,3,5$ の3種類なので $n=3$ ということです。

この素因数を文字で表します。 $p_1,p_2,\cdots ,p_n$ と置きます。これは互いに異なる $n$ 個の素数です。 $N=360$ なら、 $p_1=2$, $p_2=3$, $p_3=5$ などと置いている、ということです。順番は別にこの通りである必要はありません。

また、各素因数 $p_i$ について、 $N$ を何回割ることができるかを考えます。この回数を $a_i$ 回としましょう。 $N=360$ の場合でいうと、 $p_1=2$ なら $a_1=4$ とする、ということです。

このように文字を決めると、 $N$ を素因数分解した式は、次のようになります。\[ N=p_1^{a_1} p_2^{a_2} \cdots p_n^{a_n} \]ごつい式ですが、これは $N=360$ の場合でいうと $360=2^4\cdot 3^2 \cdot 5$ と表すことに対応しています。文字で書くとすごく複雑な気がしますが、一般的に表現しようとすると、どうしてもこのような形になってしまいます。慣れていきましょう。