Smallest Prime Factor
(lib/math/prime-factor.hpp)

• View this file on GitHub
• Last update: 2024-11-18 03:25:02+09:00
• Include: #include "lib/math/prime-factor.hpp"

Smallest Prime Factor

概要

各数に対する最小の素因数を前計算しておくことによって、素因数分解を高速に行います。

使い方

• PrimeFactor(N): $N$ までの前計算を行います。
• get(n): $n$ について素因数分解を行います。
• getPair(n): $n$ について素因数分解を行います。(素因数と個数の組が返ってきます)

計算量

• PrimeFactor(N): $\mathrm{O}(N \log \log N)$
• get(n): $\mathrm{O}(\log N)$
• getPair(n): $\mathrm{O}(\log N)$

Code

#pragma once

/**
 * @brief Smallest Prime Factor
 * @docs docs/math/prime-factor.md
 */

#include <vector>

template <typename T>
struct PrimeFactor{
    std::vector<T> spf;
    PrimeFactor(T N){ init(N); }
    void init(T N){
        spf.assign(N + 1, 0);
        for(T i = 0; i <= N; i++) spf[i] = i;
        for(T i = 2; i * i <= N; i++) {
            if(spf[i] == i) {
                for(T j = i * i; j <= N; j += i){
                    if(spf[j] == j){
                        spf[j] = i;
                    }
                }
            }
        }
    }

    std::vector<T> get(T n){
        std::vector<T> res;
        while(n != 1){
            res.push_back(spf[n]);
            n /= spf[n];
        }
        return res;
    }

    std::vector<std::pair<T, int>> getPair(T n){
        std::vector<std::pair<T, int>> res;
        while(n != 1){
            T p = spf[n];
            int cnt = 0;
            while(n % p == 0){
                n /= p;
                cnt++;
            }
            res.push_back({p, cnt});
        }
        return res;
    }
};

#line 2 "lib/math/prime-factor.hpp"

/**
 * @brief Smallest Prime Factor
 * @docs docs/math/prime-factor.md
 */

#include <vector>

template <typename T>
struct PrimeFactor{
    std::vector<T> spf;
    PrimeFactor(T N){ init(N); }
    void init(T N){
        spf.assign(N + 1, 0);
        for(T i = 0; i <= N; i++) spf[i] = i;
        for(T i = 2; i * i <= N; i++) {
            if(spf[i] == i) {
                for(T j = i * i; j <= N; j += i){
                    if(spf[j] == j){
                        spf[j] = i;
                    }
                }
            }
        }
    }

    std::vector<T> get(T n){
        std::vector<T> res;
        while(n != 1){
            res.push_back(spf[n]);
            n /= spf[n];
        }
        return res;
    }

    std::vector<std::pair<T, int>> getPair(T n){
        std::vector<std::pair<T, int>> res;
        while(n != 1){
            T p = spf[n];
            int cnt = 0;
            while(n % p == 0){
                n /= p;
                cnt++;
            }
            res.push_back({p, cnt});
        }
        return res;
    }
};

Back to top page