Math/prime_factorization.cpp

• View this file on GitHub
• Last update: 2022-05-27 16:58:03+09:00

Verified with

• test/aoj/NTL_1_A.test.cpp

Code

vector<pair<int64,int32>> prime_factorization(int64 n){
  assert(n >= 1);
  vector<pair<int64,int32>> res;
  for(int64 p = 2; p * p <= n; ++p){
    int32 cnt = 0;
    while(n % p == 0){
      ++cnt;
      n /= p;
    }
    if(cnt > 0)res.emplace_back(p,cnt);
  }
  if(n > 1){
    res.emplace_back(n,1);
  }
  return res;
}

#line 1 "Math/prime_factorization.cpp"
vector<pair<int64,int32>> prime_factorization(int64 n){
  assert(n >= 1);
  vector<pair<int64,int32>> res;
  for(int64 p = 2; p * p <= n; ++p){
    int32 cnt = 0;
    while(n % p == 0){
      ++cnt;
      n /= p;
    }
    if(cnt > 0)res.emplace_back(p,cnt);
  }
  if(n > 1){
    res.emplace_back(n,1);
  }
  return res;
}

Back to top page