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>

#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;
}