素因数分解テーブル
(C++/math/primefactortable.hpp)

• View this file on GitHub
• Last update: 2024-03-29 03:01:20+09:00
• Include: #include "C++/math/primefactortable.hpp"

Required by

• テンプレート (C++/template.hpp)

Verified with

• test/aarray.test.cpp
• test/add.test.cpp
• test/add128.test.cpp
• test/extgcd.test.cpp
• test/fwtree.test.cpp
• test/m_add.test.cpp
• test/parsum.test.cpp
• test/s_rmq.test.cpp
• test/segtree.test.cpp
• test/sr_sum.test.cpp
• test/stable.test.cpp
• test/uf.test.cpp

Code

#pragma once

#include <vector>
#include <map>
#include <numeric>
namespace Heileden {
struct p_fact {
    std::vector<int64_t> spf;
    p_fact(const int n): spf(n + 1){
        std::iota(spf.begin(), spf.end(), 0);
        for(int64_t i = 2; i * i <= n; ++i) {
            if(spf[i] == i) {
                for(int64_t j = i * i; j <= n; j += i) {
                    if(spf[j]==j) {
                        spf[j]=i;
                    }
                }
            }
        }
    }
    std::map<int, int> get(int n) {
        std::map<int, int> m;
        while(n != 1) {
            m[spf[n]]++;
            n /= spf[n];
        }
        return m;
    }
};
}

/**
 * @brief 素因数分解テーブル
 */

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

#include <vector>
#include <map>
#include <numeric>
namespace Heileden {
struct p_fact {
    std::vector<int64_t> spf;
    p_fact(const int n): spf(n + 1){
        std::iota(spf.begin(), spf.end(), 0);
        for(int64_t i = 2; i * i <= n; ++i) {
            if(spf[i] == i) {
                for(int64_t j = i * i; j <= n; j += i) {
                    if(spf[j]==j) {
                        spf[j]=i;
                    }
                }
            }
        }
    }
    std::map<int, int> get(int n) {
        std::map<int, int> m;
        while(n != 1) {
            m[spf[n]]++;
            n /= spf[n];
        }
        return m;
    }
};
}

/**
 * @brief 素因数分解テーブル
 */

Back to top page