素因数分解
(C++/math/primefactor.hpp)

• View this file on GitHub
• Last update: 2025-06-14 01:07:36+09:00
• Include: #include "C++/math/primefactor.hpp"

Code

#pragma once

#include <vector>
#include <utility>
namespace man {
template <std::integral T> inline std::vector<std::pair<T, int>> prmfct(T n) noexcept {
    std::vector<std::pair<T, int>> ret;
    for(long long i = 2; i * i <= n; ++i) {
        if(n % i != 0) {
            continue;
        }
        int tmp = 0;
        while(n % i == 0) {
            tmp++;
            n /= i;
        }
        ret.emplace_back(i, tmp);
    }
    if(n != 1) {
        ret.emplace_back(n, 1);
    }
    return ret;
}
}

/**
 * @brief 素因数分解
 */

#line 2 "C++/math/primefactor.hpp"

#include <vector>
#include <utility>
namespace man {
template <std::integral T> inline std::vector<std::pair<T, int>> prmfct(T n) noexcept {
    std::vector<std::pair<T, int>> ret;
    for(long long i = 2; i * i <= n; ++i) {
        if(n % i != 0) {
            continue;
        }
        int tmp = 0;
        while(n % i == 0) {
            tmp++;
            n /= i;
        }
        ret.emplace_back(i, tmp);
    }
    if(n != 1) {
        ret.emplace_back(n, 1);
    }
    return ret;
}
}

/**
 * @brief 素因数分解
 */

Back to top page