約数の個数(線形篩)
(C++/math/divisortable.hpp)

• View this file on GitHub
• Last update: 2026-01-04 19:41:25+09:00
• Include: #include "C++/math/divisortable.hpp"

Depends on

• Sieve of Eratosthenes (C++/math/primetable.hpp)

Code

#pragma once

#include "C++/math/primetable.hpp"
namespace man {
struct d_table {
private:
    std::vector<int> ret, cnt;
    p_table pt;
public:
    d_table(const int n): ret(n + 1), cnt(n + 1), pt(n){
        const auto is_prime = pt.SoE;
        const auto primes = pt.get();
        for(const auto i: std::views::iota(2, n + 1)) {
            if(is_prime[i]) {
                ret[i] = 2;
                cnt[i] = 1;
            }
            for(const auto &p: primes) {
                if(static_cast<long long>(i) * p > n) {
                    break;
                }
                if(i % p == 0) {
                    cnt[i * p] = cnt[i] + 1;
					ret[i * p] = ret[i] / (cnt[i] + 1) * (cnt[i * p] + 1);
					break;
				} else {
					cnt[i * p] = 1;
					ret[i * p] = ret[i] * 2;
				}
            }
        }
    }
    inline std::vector<int> get() noexcept { return ret; }
};
}

/**
 * @brief 約数の個数(線形篩)
 */

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

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

#include <vector>
#include <ranges>
namespace man {
struct p_table {
    std::vector<int> SoE;
    p_table(const int n): SoE(n + 1, 1) {
        SoE[0] = SoE[1] = 0;
        for(const long long i: std::views::iota(2, n + 1)) {
            if(!SoE[i]) {
                continue;
            }
            for(long long j = i * i; j <= n; j += i) {
                SoE[j] = 0;
            }
        }
    }
    std::vector<int> get() {
        std::vector<int> p;
        for(const auto i: std::views::iota(2, std::ssize(SoE))) {
            if(SoE[i]) {
                p.emplace_back(i);
            }
        }
        return p;
    }
};
}

/**
 * @brief Sieve of Eratosthenes
 */
#line 4 "C++/math/divisortable.hpp"
namespace man {
struct d_table {
private:
    std::vector<int> ret, cnt;
    p_table pt;
public:
    d_table(const int n): ret(n + 1), cnt(n + 1), pt(n){
        const auto is_prime = pt.SoE;
        const auto primes = pt.get();
        for(const auto i: std::views::iota(2, n + 1)) {
            if(is_prime[i]) {
                ret[i] = 2;
                cnt[i] = 1;
            }
            for(const auto &p: primes) {
                if(static_cast<long long>(i) * p > n) {
                    break;
                }
                if(i % p == 0) {
                    cnt[i * p] = cnt[i] + 1;
					ret[i * p] = ret[i] / (cnt[i] + 1) * (cnt[i * p] + 1);
					break;
				} else {
					cnt[i * p] = 1;
					ret[i * p] = ret[i] * 2;
				}
            }
        }
    }
    inline std::vector<int> get() noexcept { return ret; }
};
}

/**
 * @brief 約数の個数(線形篩)
 */

Back to top page