test/factorize.test.cpp

View this file on GitHub
Last update: 2022-01-07 22:21:35+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_A

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_A"
#include "../math/factorize.cpp"
#include "../utility/int_alias.cpp"
#include <iostream>

int main() {
    u32 n;
    std::cin >> n;
    std::cout << n << ':';
    for (auto [p, e]: factorize(n)) {
        while (e--) {
            std::cout << ' ' << p;
        }
    }
    std::cout << '\n';
    return 0;
}

#line 1 "test/factorize.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_A"
#line 2 "math/factorize.cpp"
#include <cassert>
#include <utility>
#include <vector>

template <class T> std::vector<std::pair<T, int>> factorize(T x) {
    assert(x > 0);
    std::vector<std::pair<T, int>> ret;
    for (T p = 2; p * p <= x; ++p) {
        if (x % p == 0) {
            int e = 0;
            while (x % p == 0) {
                x /= p;
                e += 1;
            }
            ret.emplace_back(p, e);
        }
    }
    if (x > 1) ret.emplace_back(x, 1);
    return ret;
}
#line 2 "utility/int_alias.cpp"
#include <cstdint>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
#line 4 "test/factorize.test.cpp"
#include <iostream>

int main() {
    u32 n;
    std::cin >> n;
    std::cout << n << ':';
    for (auto [p, e]: factorize(n)) {
        while (e--) {
            std::cout << ' ' << p;
        }
    }
    std::cout << '\n';
    return 0;
}