素数判定、約数列挙
(lib/math/prime.hpp)

• View this file on GitHub
• Last update: 2024-10-21 04:45:56+09:00
• Include: #include "lib/math/prime.hpp"

素数判定、約数列挙

概要

素数判定、約数列挙などのアルゴリズムの詰め合わせです。

数が大きい場合には Pollard’s Rho の使用を推奨します。

使い方

• prime::isPrime(N): $N$ が素数かどうかを判定します。
• prime::factrize(N): $N$ について素因数分解をします。
• prime::divisor(N): $N$ の約数を昇順に列挙します。
• prime::sieve(N): $2$ から $N$ までの素因数の個数を返します。(エラトステネスのふるい)

計算量

• prime::isPrime(N): $\mathrm{O}(\sqrt N)$
• prime::factrize(N): $\mathrm{O}(\sqrt N)$
• prime::divisor(N): $\mathrm{O}(\sqrt N)$
• prime::sieve(N): $\mathrm{O}(N \log \log N)$

Verified with

• test/aoj/alds1/alds1_1_c.test.cpp
• test/aoj/ntl/ntl_1_a.test.cpp
• test/yukicoder/yuki_888_1.test.cpp

Code

#pragma once

/**
 * @brief 素数判定、約数列挙
 * @docs docs/math/prime.md
 */

namespace prime{

    template <typename T>
    bool isPrime(T n){
        switch(n) {
        case 0: // fall-through
        case 1: return false;
        case 2: return true;
        }

        if(n % 2 == 0) return false;

        for(T i = 3; i * i <= n; i += 2){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }

    template <typename T>
    vector<pair<T, T>> factorize(T n) {
        vector<pair<T, T>> ret;
        for(T i = 2; i * i <= n; i++) {
            if(n % i != 0) continue;
            T tmp = 0;
            while(n % i == 0) {
                tmp++;
                n /= i;
            }
            ret.push_back(make_pair(i, tmp));
        }
        if(n != 1) ret.push_back(make_pair(n, 1));
        return ret;
    }

    template <typename T>
    vector<T> divisor(T n){
        T rt = sqrt(n);
        vector<T> res, resB;
        for(T i = 1; i * i <= n; i++){
            if(n % i == 0){
                res.push_back(i);
                T j = n / i;
                if(j != rt){
                    resB.push_back(j);
                }
            }
        }
        for(int i = (int) resB.size() - 1; i >= 0; i--){
            res.push_back(resB[i]);
        }
        return res;
    }
}

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

/**
 * @brief 素数判定、約数列挙
 * @docs docs/math/prime.md
 */

namespace prime{

    template <typename T>
    bool isPrime(T n){
        switch(n) {
        case 0: // fall-through
        case 1: return false;
        case 2: return true;
        }

        if(n % 2 == 0) return false;

        for(T i = 3; i * i <= n; i += 2){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }

    template <typename T>
    vector<pair<T, T>> factorize(T n) {
        vector<pair<T, T>> ret;
        for(T i = 2; i * i <= n; i++) {
            if(n % i != 0) continue;
            T tmp = 0;
            while(n % i == 0) {
                tmp++;
                n /= i;
            }
            ret.push_back(make_pair(i, tmp));
        }
        if(n != 1) ret.push_back(make_pair(n, 1));
        return ret;
    }

    template <typename T>
    vector<T> divisor(T n){
        T rt = sqrt(n);
        vector<T> res, resB;
        for(T i = 1; i * i <= n; i++){
            if(n % i == 0){
                res.push_back(i);
                T j = n / i;
                if(j != rt){
                    resB.push_back(j);
                }
            }
        }
        for(int i = (int) resB.size() - 1; i >= 0; i--){
            res.push_back(resB[i]);
        }
        return res;
    }
}

Back to top page