素因数分解

コード例

C++

using ll = long long;
using P = pair<ll, ll>;

vector<P> prime_fact(ll n) {
  vector<P> ret;

  for (ll i = 2; i * i <= n; i++) {
    if (n % i != 0) continue;

    ll cnt = 0;
    while (n % i == 0) {
      cnt++;
      n /= i;
    }

    ret.push_back({i, cnt});
  }

  if (n >= 2) {
    ret.push_back({n, 1});
  }

  return ret;
}

TypeScript

type PrimeFact = {
  prime: number;
  cnt: number;
};

function primeFact(n: number): PrimeFact[] {
  let ret: PrimeFact[] = [];

  for (let i = 2; i * i <= n; i++) {
    if (n % i !== 0) continue;

    let cnt = 0;
    while (n % i === 0) {
      cnt++;
      n /= i;
    }

    ret.push({ prime: i, cnt });
  }

  if (n >= 2) {
    ret.push({ prime: n, cnt: 1 });
  }

  return ret;
}

解説/アルゴリズム

渡された数を 2 で割れるだけ割り、その数をカウント、次に 3 で割れるだけ割り、その数をカウント・・・、と、 2 から順番に試し割りをしていき、カウントが 1 以上になるなら、割る数とカウントをペアにして保存する。

8 や 9 のような合成数で割ろうとする場合、既にその合成数の約数である素数で試し割りをしているので、その数でのカウントが 1 以上になることはない。

試し割りの上限は N ではなく $\sqrt{N}$ まで見れば十分となる。

最終的に残った数が 2 以上なら、その数は素数ということになるので、その素数とカウント 1 をペアにして保存をする。