math/prime_factor.hpp

• View this file on GitHub
• Last update: 2023-02-06 17:52:27+09:00
• Include: #include "math/prime_factor.hpp"

Required by

• math/totient.hpp

Verified with

• verify/aoj_ntl/aoj_ntl_1_a.test.cpp
• verify/aoj_ntl/aoj_ntl_1_d.test.cpp

Code

#pragma once

std::map<long long, int> prime_factor(long long n) {
    std::map<long long, int> res;
    for (long long i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            res[i]++;
            n /= i;
        }
    }
    if (n != 1) res[n]++;
    return res;
}

#line 2 "math/prime_factor.hpp"

std::map<long long, int> prime_factor(long long n) {
    std::map<long long, int> res;
    for (long long i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            res[i]++;
            n /= i;
        }
    }
    if (n != 1) res[n]++;
    return res;
}

Back to top page