素因数分解 (prime_factorize)

目的

素因数分解をする。

オーダー

O(√N)

コード

vector<pair<long long, long long>> prime_factorize(long long N)
{
  vector<pair<long long, long long>> res;
  for (long long a = 2; a * a <= N; ++a)
  {
    if (N % a != 0)
      continue;
    long long ex = 0; // 指数

    // 割れる限り割り続ける
    while (N % a == 0)
    {
      ++ex;
      N /= a;
    }

    // その結果を push
    res.push_back({a, ex});
  }

  // 最後に残った数について
  if (N != 1)
    res.push_back({N, 1});
  return res;
}

コードテスト

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
#define REP(i, x) for (ll i = 0; i < (ll)(x); i++)

vector<pair<long long, long long>> prime_factorize(long long N)
{
  vector<pair<long long, long long>> res;
  for (long long a = 2; a * a <= N; ++a)
  {
    if (N % a != 0)
      continue;
    long long ex = 0; // 指数

    // 割れる限り割り続ける
    while (N % a == 0)
    {
      ++ex;
      N /= a;
    }

    // その結果を push
    res.push_back({a, ex});
  }

  // 最後に残った数について
  if (N != 1)
    res.push_back({N, 1});
  return res;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll A,B;

  cin >> A;

  const auto &res = prime_factorize(A);
  REP(i,res.size()){
    cout << "{" << res.at(i).first << "^" << res.at(i).second << "}" << endl;
  }
}

720
{2^4}
{3^2}
{5^1}

出典

qiita.com