C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title 数学/素因数分解 * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A */ #include <iostream> #include <utility> #include <vector> #include "emthrm/math/prime_factorization.hpp" int main() { int n; std::cin >> n; const std::vector<std::pair<int, int>> ans = emthrm::prime_factorization(n); std::cout << n << ": "; for (int i = 0; std::cmp_less(i, ans.size()); ++i) { for (int j = 0; j < ans[i].second; ++j) { std::cout << ans[i].first << " \n"[std::cmp_equal(i + 1, ans.size()) && j + 1 == ans[i].second]; } } return 0; }
#line 1 "test/math/prime_factorization.test.cpp" /* * @title 数学/素因数分解 * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A */ #include <iostream> #include <utility> #include <vector> #line 1 "include/emthrm/math/prime_factorization.hpp" #line 6 "include/emthrm/math/prime_factorization.hpp" namespace emthrm { template <typename T> std::vector<std::pair<T, int>> prime_factorization(T n) { std::vector<std::pair<T, int>> res; for (T i = 2; i * i <= n; ++i) { if (n % i == 0) [[unlikely]] { int exponent = 0; for (; n % i == 0; n /= i) { ++exponent; } res.emplace_back(i, exponent); } } if (n > 1) res.emplace_back(n, 1); return res; } } // namespace emthrm #line 12 "test/math/prime_factorization.test.cpp" int main() { int n; std::cin >> n; const std::vector<std::pair<int, int>> ans = emthrm::prime_factorization(n); std::cout << n << ": "; for (int i = 0; std::cmp_less(i, ans.size()); ++i) { for (int j = 0; j < ans[i].second; ++j) { std::cout << ans[i].first << " \n"[std::cmp_equal(i + 1, ans.size()) && j + 1 == ans[i].second]; } } return 0; }