Test/Math/Prime.test.cpp

• View this file on GitHub
• Last update: 2024-12-27 17:07:26+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_A

Depends on

• Library/Math/Prime.hpp

Code

#define PROBLEM \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_A"

#include "./../../Library/Math/Prime.hpp"


#include <algorithm>

#include <iostream>


using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';

signed main() {
  ll n;
  cin >> n;

  auto prime = mtd::Prime(1e5);
  auto fc = prime.factorization(n);

  std::vector<ll> ans;
  for (const auto& [x, c] : fc)
    for (int i = 0; i < c; ++i) { ans.emplace_back(x); }
  std::sort(ans.begin(), ans.end());

  cout << n << ": ";
  for (unsigned int i = 0; i < ans.size(); ++i) {
    cout << ans[i] << (i + 1 < ans.size() ? " " : "\n");
  }
}

#line 1 "Test/Math/Prime.test.cpp"
#define PROBLEM \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_A"

#line 2 "Library/Math/Prime.hpp"

#include <deque>

#include <unordered_map>

#include <vector>


namespace mtd {
  class Prime {
    const long long n;
    const std::deque<long long> p_list;

    static inline auto linearSieve(long long n) {
      std::deque<long long> p_list;
      std::vector<long long> lpf(n + 1);
      for (int d = 2; d < n + 1; ++d) {
        if (!lpf[d]) {
          lpf[d] = d;
          p_list.emplace_back(d);
        }
        for (const auto& p : p_list) {
          if (p * d > n || p > lpf[d]) { break; }
          lpf[p * d] = p;
        }
      }
      return std::tuple{p_list, lpf};
    }

  public:
    Prime(long long _n) : n(_n), p_list(std::get<0>(linearSieve(_n))) {}

    /* nはsqrt(max(x))あれば十分なので気を付ける */
    auto factorization(long long x) const {
      std::unordered_map<long long, long long> table;
      for (const auto& p : p_list) {
        while (x % p == 0) {
          table[p]++;
          x /= p;
        }
      }
      if (x > 1) { table[x]++; }
      return table;
    }
    auto getPList() const { return p_list; }
  };
}  // namespace mtd

#line 5 "Test/Math/Prime.test.cpp"

#include <algorithm>

#include <iostream>


using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';

signed main() {
  ll n;
  cin >> n;

  auto prime = mtd::Prime(1e5);
  auto fc = prime.factorization(n);

  std::vector<ll> ans;
  for (const auto& [x, c] : fc)
    for (int i = 0; i < c; ++i) { ans.emplace_back(x); }
  std::sort(ans.begin(), ans.end());

  cout << n << ": ";
  for (unsigned int i = 0; i < ans.size(); ++i) {
    cout << ans[i] << (i + 1 < ans.size() ? " " : "\n");
  }
}

Back to top page