verify/aoj-NTL_1_A-prime_factorize.test.cpp

View this file on GitHub
Last update: 2025-07-03 00:41:25+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_A

Depends on

algorithm/Math/NumberTheory/prime_factorize.hpp

Code

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

#include <iostream>

#include "../algorithm/Math/NumberTheory/prime_factorize.hpp"

int main() {
    int n;
    std::cin >> n;

    const auto &&pf = algorithm::prime_factorize(n);

    std::cout << n << ":";
    for(const auto &[p, cnt] : pf) {
        for(int i = 0; i < cnt; ++i) std::cout << " " << p;
    }
    std::cout << std::endl;
}

#line 1 "verify/aoj-NTL_1_A-prime_factorize.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_A"

#include <iostream>

#line 1 "algorithm/Math/NumberTheory/prime_factorize.hpp"



#include <cassert>
#include <map>

namespace algorithm {

// 素因数分解．O(√N).
template <typename Type>
std::map<Type, int> prime_factorize(Type n) {
    assert(n >= 0);
    std::map<Type, int> res;  // res[p]:=(自然数nに含まれる素因数pの個数).
    for(; n % 2 == 0; n /= 2) res[2]++;
    for(Type p = 3; p * p <= n; p += 2) {
        for(; n % p == 0; n /= p) res[p]++;
    }
    if(n > 1) res[n] = 1;
    return res;
}

}  // namespace algorithm


#line 6 "verify/aoj-NTL_1_A-prime_factorize.test.cpp"

int main() {
    int n;
    std::cin >> n;

    const auto &&pf = algorithm::prime_factorize(n);

    std::cout << n << ":";
    for(const auto &[p, cnt] : pf) {
        for(int i = 0; i < cnt; ++i) std::cout << " " << p;
    }
    std::cout << std::endl;
}