【競プロ】素因数分解と約数の個数

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

ここでは素因数分解をすることで、約数の個数が数えやすくなる、という話を見ていきます。ここでは、正の約数のみを扱うことにします。素因数分解と約数と倍数にも関連する話です。競プロ記事の一覧はこちら。

📘 目次

小さな数字での話

素因数分解は、正の整数を素数の積で表すことをいうのでした。例えば、 $12$ なら $2^2\times 3$ と表すのが素因数分解です。このように表すことのメリットの一つに、約数を調べやすくなる、というものがあります。どういうことか、見ていきましょう。

$12$ の正の約数を順番に並べると、$1$, $2$, $3$, $4$, $6$, $12$ となります。これらを、2で何回割れるか、3で何回割れるか、で分類してみると、次のような表になります。

	3で0回割れる	3で1回割れる
2で0回割れる	$1$	$3$
2で1回割れる	$2$	$6$
2で2回割れる	$4$	$12$

約数もそれぞれ素因数分解してみると、 $1$, $2$, $3$, $2^2$, $2\times 3$, $2^2\times 3$ となります。こうしてみると、2のパーツと3のパーツを組み合わせてできていることがわかります。次のように表にしてみると、さらに構造が分かりやすくなります。

	$3^0$	$3^1$
$2^0$	$2^0\cdot 3^0$	$2^0\cdot 3^1$
$2^1$	$2^1\cdot 3^0$	$2^1\cdot 3^1$
$2^2$	$2^2\cdot 3^0$	$2^2\cdot 3^1$

$2$, $3$ は、 $2^1$, $3^1$ と表しています。また、 $1$ は $2^0$, $3^0$ などと表しています。慣れるまでは見にくいですが、このように書くといいことが起こっています。 $2,3$ の指数の部分（右上の数字のこと）に注目してみましょう。 $2$ の指数は $0$ から $2$ まで、 $3$ の指数は $0,1$ となっています。これらを組み合わせることで、約数の個数が6個だとわかります。

素因数分解をしたときに $2^2\times 3^1$ となることから、約数を素因数分解したときにありえる組み合わせは、 $2$ の指数は3通り、 $3$ の指数が2通りだとわかるので、約数の個数が $3\times 2$ 個になることがわかります。

もう少し大きな数字での話

もう少し大きな数を使って考えてみましょう。 $360$ を考えます。これを素因数分解すれば\[ 360=2^3\times 3^2 \times 5 \]となります。次に、 $360$ の約数の個数を、列挙しないで考えます。正の整数 $a$ が約数の場合、 $360\div a$ が割り切れるということです。この $a$ を素因数分解すると、どのような形になりうるでしょうか（参考：素因数分解と約数と倍数）。

まず、 $a$ を素因数分解したときに、 $7$ とか $13$ といった素数が出てくることはありえません。 $2^3\times 3^2 \times 5$ が $a$ で割り切れるなら、素因数は $2,3,5$ だけしか登場しないはずです。

しかも、指数の大きさも制限されます。例えば、 $360=2^3\times 3^2 \times 5$ は、 $3^2$ や $3^0$ では割りきれますが、 $3^3$ や $3^4$ では割り切れません。 $3$ では2回までしか割り切れません。他の素因数についても同様です。 $2^x$ の $x$ は0から3まで、 $5^z$ は0から1までとなります。

こうしたことから、 $360$ の正の約数は、次のように表すことができます。\[ 2^x\times 3^y \times 5^z \]ここで、 $x=0,1,2,3$ で、 $y=0,1,2$ で、 $z=0, 1$ の値だけをとります。それぞれ、4通り、3通り、2通りなので、 $360$ の正の約数の個数は、 \[ 4\times 3\times 2=24 \]個であることがわかります。

列挙しなくても正の約数の個数がわかる、という点が便利なんですね。約数を具体的に求める必要がないときには、素因数分解を使って約数の個数を求めることができます。

一般的な数字での話

最後に、一般な話をしましょう。正の整数 $N$ を素因数分解したとき、 $n$ 個の素数 $p_1, p_2, p_3,\cdots, p_n$ とその指数 $a_1, a_2,a_3,\cdots, a_n $ を使って\[ N=p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3}\cdots p_n^{a_n} \]になるとします。このとき、ここまでの内容と同じようにして、正の約数は、\[ p_1^{x_1}\cdot p_2^{x_2}\cdot p_3^{x_3}\cdots p_n^{x_n} \]で表せます。ここで、 $x_i$ は、 $0$ 以上 $a_i$ 以下の整数です。ごつい式ですが、素因数分解した後の式を一般的に表しているだけです。

このように表すことができれば、約数の個数も計算できます。各 $p_i$ の指数の選び方が $a_i+1$ 通りあり、これがそれぞれの素因数について成り立つことから、\[ (a_1+1)(a_2+1)(a_3+1)\cdots (a_n+1) \]個となります。

逆に考えると、約数の個数からもとの数字の候補を挙げることもできるようになります。例えば、正の約数が6個になる数を考えてみましょう。素因数分解をして $2^a$ の形になるとすると、約数の個数は $a+1$ 個となるので $a=5$ しかありません。 $2^5=32$ の約数を列挙して確かめてみましょう。また、 $3^b\cdot 5^c$ の形になるとすると、約数の個数は $(b+1)(c+1)$ となるので、例えば $b=2,c=1$ などが該当します。\[ 3^2\cdot 5^1=45 \]ですが、これの約数が6個になるか確かめてみましょう。約数の個数からもとの数を考える、というのは、素因数分解をしないとなかなか考えづらいです。

ここまでの内容を踏まえると、AtCoder ABC 106 B - 105 に挑戦できます。これは、範囲内のすべての整数に対して約数の個数を数えていく方法もあります（というか、普通はそうします）が、ここで見た内容を踏まえれば、正の約数を8個持つ整数を直接求めることができます（難易度は少し高いですが）。該当する整数は、解説にすべて載っているので、考えた後に見てみましょう。

コードで表現する

ここまでの話をもとに、受け取った正の整数に対して、正の約数を数えるコードを書いてみます。各素因数について、指数を調べていきます。指数が $a_i$ 個なら、約数の個数を $(a_i+1)$ 倍して、次の素因数へと移っていく、というのを繰り返していきます。

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

int main() {
  int a, ans = 1;
  cin >> a;

  for (int i = 2; i <= sqrt(a); i++) {
    int cnt = 0;
    while (a % i == 0) {
      cnt++;
      a /= i;
    }
    ans *= (cnt + 1);
    if (a == 1) break;
  }
  if (a != 1) ans *= 2;

  cout << ans;
  return 0;
}

最後に素因数が1つだけ残るとき（例えば先ほどの例で見た360の場合など）には、 a != 1 となります。この場合は、指数が1なので、個数を2倍します。

倍数と約数では、正の約数を列挙するコードを見ました。このコードを利用しても約数を数えることはできます。見た目もやっている内容も大きく異なりますが、同じ結果が得られます。