素因数分解 (Math/prime_factorize.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-09-30 18:16:55+09:00
• Include: #include "Math/prime_factorize.hpp"

prime_factorize

vector<pair<long long, long long>> prime_factorize(long long N)

入力された整数Nを$\sqrt{N}$以下の値を試し割りして素因数分解します。
素因数分解の結果をvector<pair<long long, long long>>として返します。
各ペアは、最初の要素が素因数、2番目の要素がその素因数の指数を示します。

制約

• $0 \lt N$

計算量

• $O(\sqrt{N})$

Required by

• Zobrist Hash (立方数判定) (Hash/zobrist_cubic_hash.hpp)

Verified with

• test/Hash/zobrist_hash/abc238-g.cpp
• test/Math/enumerate_divisor/aoj-ITP1_3_D.test2.cpp
• test/Math/prime_factorize/aoj-NTL_1_A.test.cpp

Code

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

vector<pair<long long, long long>> prime_factorize(long long N)
{
    assert(0 < N);

    long long tempN = N;
    vector<pair<long long, long long>> dst;
    for (long long i = 2; i * i <= tempN; i++)
    {
        if (N % i == 0)
        {
            dst.push_back(make_pair(i, 0));
            while (N % i == 0)
            {
                dst.back().second++;
                N /= i;
            }
        }
    }
    if (N != 1)
        dst.push_back(make_pair(N, 1));
    return dst;
}

#line 1 "Math/prime_factorize.hpp"
#include <bits/stdc++.h>
using namespace std;

vector<pair<long long, long long>> prime_factorize(long long N)
{
    assert(0 < N);

    long long tempN = N;
    vector<pair<long long, long long>> dst;
    for (long long i = 2; i * i <= tempN; i++)
    {
        if (N % i == 0)
        {
            dst.push_back(make_pair(i, 0));
            while (N % i == 0)
            {
                dst.back().second++;
                N /= i;
            }
        }
    }
    if (N != 1)
        dst.push_back(make_pair(N, 1));
    return dst;
}

Back to top page