test/factorization.test.cpp

• View this file on GitHub
• Last update: 2022-12-03 23:34:11+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/all/NTL_1_A

Depends on

• math/prime.cpp

Code

#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/all/NTL_1_A"
#include "../math/prime.cpp"

const int MAXN = 100000;

int main() {
    int n;
    cin >> n;
    cout << n << ':';
    Eratosthenes era(MAXN);
    era.build();
    for (const auto &p : era.factorize(n)) {
        for (int i = 0; i < p.second; i++)
            cout << ' ' << p.first;
    }
    cout << '\n';
}

#line 1 "test/factorization.test.cpp"
#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/all/NTL_1_A"
#line 3 "math/prime.cpp"
using namespace std;

// is_prime
// 整数nが素数かどうか判定する.
// 制約: n >= 1,
// 計算量: O(√n)
template <typename T>
bool is_prime(T n) {
    for (T i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return n != 1;
}

// divisor
// 整数nの因数を列挙する.
// 制約: n >= 1
// 計算量: O(√nlogn)
template <typename T>
vector<T> divisor(T n) {
    vector<T> ans;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ans.push_back(i);
            if (i != n / i) ans.push_back(n / i);
        }
    }
    sort(ans.begin(), ans.end());
    return ans;
}

// prime_factor
// 整数nを素因数分解した結果を返す.
// 制約: n >= 1
// 計算量: O(√n)
template <typename T>
vector<pair<T, int>> prime_factor(T n) {
    vector<pair<T, int>> ans;
    for (T i = 2; i * i <= n; i++) {
        int cnt = 0;
        while (n % i == 0) {
            cnt++;
            n /= i;
        }
        if (cnt > 0) ans.emplace_back(i, cnt);
    }
    if (n != 1) ans.emplace_back(n, 1);
    return ans;
}

// Eratosthenes
// n以下の整数が素数かどうか判定する
// 制約: n >= 1
struct Eratosthenes {

  private:
    int n;
    vector<int> is_primes, primes;

  public:
    Eratosthenes(int n) : n(n) {
        is_primes.assign(n + 1, 1);
    }

    // build
    // n以下の素数を全て返す
    // 計算量: O(nloglogn)
    vector<int> build() {
        is_primes[0] = is_primes[1] = 0;
        for (long long i = 2; i <= n; i++) {
            if (!is_primes[i]) continue;
            primes.push_back(i);
            for (long long j = i * i; j <= n; j += i) {
                is_primes[j] = 0;
            }
        }
        return primes;
    }

    // is_prime
    // 整数pが素数かどうか判定する
    // 制約: 1 <= p <= n
    bool is_prime(int p) {
        return is_primes[p];
    }

    // factorize
    // 整数mを素因数分解する
    // 制約: 1 <= m <= n*n
    // 計算量: O(min{n,√m})
    template <typename T>
    vector<pair<T, int>> factorize(T m) {
        vector<pair<T, int>> ans;
        for (const int &p : primes) {
            if (p > m) break;
            int count = 0;
            while (m % p == 0) {
                count++;
                m /= p;
            }
            if (count > 0) ans.emplace_back(p, count);
        }
        if (m != 1) ans.emplace_back(m, 1);
        return ans;
    }
};
#line 6 "test/factorization.test.cpp"

const int MAXN = 100000;

int main() {
    int n;
    cin >> n;
    cout << n << ':';
    Eratosthenes era(MAXN);
    era.build();
    for (const auto &p : era.factorize(n)) {
        for (int i = 0; i < p.second; i++)
            cout << ' ' << p.first;
    }
    cout << '\n';
}

Back to top page