内容別リスト/数学系/素因数分解 - 競技プログラミング用 知識集積所

---

雑な説明

与えられた数を素数の積に分解するアルゴリズム。
毎回O(n)かかるものと、前処理にO(n*loglogn)かかるがその後は毎回O(logn)ですむものがある。

レベル

ABCのC問題以降。

アルゴリズム内容1

素数判定と同じ要領で2から小さい順に割っていく。
割りきれる場合、それが何回割れるか確認し、出力に詰める。
その際、一度調べた素数については二度と調べないので、本当に割ってしまうとよい。
平方が残っている数より大きくなれば残ったものは素数である。
O(√n)で済むが、計算結果の使いまわしが効かないので、大量に素因数分解するには不向き。

C++での実際の参考コードは以下。

vector<pair<int,int>> prime_factorization(int n) {
  vector<pair<int,int>> primes;
  int p = 2;
  while (p*p<=n) {
    int counter = 0;
    while (n%p==0) {
      counter++;
      n /= p;
    }
    if (counter>0) primes.emplace_back(p,counter);
    p++;
  }
  if (n>1) primes.emplace_back(n,1);
  return primes;
}

アルゴリズム内容2（D問題レベル）

エラトステネスの篩のところで解説してあるn未満の全ての数の最小素因数を求めるアルゴリズムを利用する。
その結果を利用すれば次に割れる素数は何か、それで何回割れるかもすぐわかる。
毎回の処理がO(logn)で済むが、最初にO(n*loglogn)かかる準備が必要になる。
10^9クラスのnが混ざっていると苦しい。

C++での実際の参考コードは以下。
上半分は最小素因数を求めるやつ。

vector<int> smallest_primes (int n) {
  vector<int> primes(n,-1);
  bool flag = true;
  for (int i=2; i<n; i++) {
    if (primes.at(i)!=-1) continue;
    primes.at(i) = i;
    if (!flag) continue;
    for (long long j=i*i; j<n; j+=i) {
      if (primes.at(j)==-1) primes.at(j) = i;
    }
    if (1LL*i*i>=n) flag = false;
  }
  return primes;
}

vector<pair<int,int>> prime_factorization(int n, const vector<int>& smallest_primes) {
  vector<pair<int,int>> primes;
  while (n>1) {
    int p = smallest_primes.at(n);
    int counter = 0;
    while (smallest_primes.at(n)==p) {
      counter++;
      n /= p;
    }
    primes.emplace_back(p,counter);
  }
  return primes;
}

  // main関数内
  auto vec = smallest_primes(n+1);
  auto vec2 = prime_factorization(n,vec);

main関数内で、素因数分解する可能性がある最大の数より1大きい数を渡さないといけないことに注意。

注意点

関連アルゴリズム

素数判定

素数かどうか判定するだけで、分解はしないやつ。

エラトステネスの篩

n未満の全ての素数を洗い出すアルゴリズム。
判定したい個数が多いなら、あちらを使った方が全体としては速い場合もある。

約数の個数と総和（未作成）

正の整数nに対して、その（正の）約数がいくつあるか、正の約数の総和がいくつになるかを求める。
素因数分解を利用して効率的に求めることができる。