prime/osak.hpp

• View this file on GitHub
• Last update: 2021-04-20 10:57:00+09:00
• Include: #include "prime/osak.hpp"

Depends on

• prime/factor-enumerate.hpp

Verified with

• verify/verify-unit-test/osak.test.cpp

Code

#pragma once

#include "factor-enumerate.hpp"

template <int MAX>
vector<int> osak(int n) {
  static vector<int> f = factor_enumerate(MAX);
  vector<int> ret;
  while (f[n]) ret.push_back(f[n]), n /= f[n];
  return ret;
}

template <int MAX>
vector<pair<int, int>> osak_table(int n) {
  static vector<int> f = factor_enumerate(MAX);
  vector<pair<int, int>> v;
  for (; f[n]; n /= f[n]) {
    if (v.empty() || v.back().first != f[n]) {
      v.emplace_back(f[n], 1);
    } else {
      v.back().second++;
    }
  }
  return v;
}

template <int MAX>
vector<int> osak_divisors(int n) {
  if(n == 0) return {};
  if(n == 1) return vector<int>(1, 1);
  auto p = osak_table<MAX>(n);
  vector<int> ds;

  auto dfs = [&](auto r, int i, int c) {
    if (i == (int)p.size()) {
      ds.push_back(c);
      return;
    }
    for (int j = 0; j <= p[i].second; j++) {
      r(r, i + 1, c);
      c *= p[i].first;
    }
  };

  dfs(dfs, 0, 1);
  sort(begin(ds), end(ds));
  return ds;
}

#line 2 "prime/osak.hpp"

#line 2 "prime/factor-enumerate.hpp"

vector<int> factor_enumerate(int N) {
  vector<int> lp(N + 1, 0);
  if (N < 2) return lp;
  vector<int> pr{2, 3};
  for (int i = 2; i <= N; i += 2) lp[i] = 2;
  for (int i = 3; i <= N; i += 6) lp[i] = 3;
  for (int i = 5, d = 4; i <= N; i += d = 6 - d) {
    if (lp[i] == 0) {
      lp[i] = i;
      pr.push_back(i);
    }
    for (int j = 2; j < (int)pr.size() && i * pr[j] <= N; ++j) {
      lp[i * pr[j]] = pr[j];
      if (pr[j] == lp[i]) break;
    }
  }
  return lp;
}
#line 4 "prime/osak.hpp"

template <int MAX>
vector<int> osak(int n) {
  static vector<int> f = factor_enumerate(MAX);
  vector<int> ret;
  while (f[n]) ret.push_back(f[n]), n /= f[n];
  return ret;
}

template <int MAX>
vector<pair<int, int>> osak_table(int n) {
  static vector<int> f = factor_enumerate(MAX);
  vector<pair<int, int>> v;
  for (; f[n]; n /= f[n]) {
    if (v.empty() || v.back().first != f[n]) {
      v.emplace_back(f[n], 1);
    } else {
      v.back().second++;
    }
  }
  return v;
}

template <int MAX>
vector<int> osak_divisors(int n) {
  if(n == 0) return {};
  if(n == 1) return vector<int>(1, 1);
  auto p = osak_table<MAX>(n);
  vector<int> ds;

  auto dfs = [&](auto r, int i, int c) {
    if (i == (int)p.size()) {
      ds.push_back(c);
      return;
    }
    for (int j = 0; j <= p[i].second; j++) {
      r(r, i + 1, c);
      c *= p[i].first;
    }
  };

  dfs(dfs, 0, 1);
  sort(begin(ds), end(ds));
  return ds;
}

Back to top page