#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A" #include <iostream> #include "../../Math/Number-Theory/prime-factorize.hpp" using namespace std; int main() { int n; cin >> n; cout << n << ":"; for (const auto [value, cnt] : primeFactorize(n)) { for (int i = 0; i < cnt; ++i) cout << ' ' << value; } cout << endl; }
#line 1 "test/AOJ/NTL_1_A-Prime-Factorize.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A" #include <iostream> #line 2 "Math/Number-Theory/prime-factorize.hpp" #include <map> /** * @brief primeFactorize() (素因数分解 $O(\sqrt n)$) */ template <class Integer> std::map<Integer, int> primeFactorize(Integer n) { std::map<Integer, int> res; for (Integer i = 2; i * i <= n; ++i) { while (n % i == 0) { ++res[i]; n /= i; } } if (n != 1) res[n] = 1; return res; } #line 6 "test/AOJ/NTL_1_A-Prime-Factorize.test.cpp" using namespace std; int main() { int n; cin >> n; cout << n << ":"; for (const auto [value, cnt] : primeFactorize(n)) { for (int i = 0; i < cnt; ++i) cout << ' ' << value; } cout << endl; }