素因数分解
(library/number/prime/prime_fact.hpp)

• View this file on GitHub
• Last update: 2026-01-15 10:11:56+09:00
• Include: #include "library/number/prime/prime_fact.hpp"

素因数分解

できること

• 整数Nの<素因数, 個数>のmapを作る

計算量

$O(\sqrt N)$

使い方

map<int, int> pf = prime_fact(N);

Verified with

• エラトステネスの篩のテスト (tests/number.prime.eratosthenes.test.cpp)
• 素因数分解のテスト (tests/number.prime.prime_fact.test.cpp)

Code

#pragma once
map<int, int> prime_fact(int N) {
    map<int, int> P;
    for (int i = 2; i * i <= N; ++i) {
        while (N % i == 0) {
            ++P[i];
            N /= i;
        }
    }
    if (N > 1) ++P[N];
    return P;
}

#line 2 "library/number/prime/prime_fact.hpp"
map<int, int> prime_fact(int N) {
    map<int, int> P;
    for (int i = 2; i * i <= N; ++i) {
        while (N % i == 0) {
            ++P[i];
            N /= i;
        }
    }
    if (N > 1) ++P[N];
    return P;
}

Back to top page