Euler's Phi-function(table)
(C++/math/phitable.hpp)

• View this file on GitHub
• Last update: 2025-06-06 22:43:06+09:00
• Include: #include "C++/math/phitable.hpp"

Verified with

• test/phi_table.test.cpp

Code

#pragma once

#include <vector>
#include <numeric>
#include <ranges>
namespace man {
struct phi_table {
private:
    int n;
	std::vector<int> euler;
public:
	phi_table(const int n_): n(n_), euler(n_ + 1) {
		std::iota(euler.begin(), euler.end(), 0);
		for(const auto i: std::views::iota(2, n + 1)) {
			if(euler[i] == i) {
				for(int j = i; j <= n; j += i) {
					euler[j] = euler[j] / i * (i - 1);
				}
			}
		}
	}
	inline std::vector<int> get() const noexcept { return euler; }
};
}

/**
 * @brief Euler's Phi-function(table)
 */

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

#include <vector>
#include <numeric>
#include <ranges>
namespace man {
struct phi_table {
private:
    int n;
	std::vector<int> euler;
public:
	phi_table(const int n_): n(n_), euler(n_ + 1) {
		std::iota(euler.begin(), euler.end(), 0);
		for(const auto i: std::views::iota(2, n + 1)) {
			if(euler[i] == i) {
				for(int j = i; j <= n; j += i) {
					euler[j] = euler[j] / i * (i - 1);
				}
			}
		}
	}
	inline std::vector<int> get() const noexcept { return euler; }
};
}

/**
 * @brief Euler's Phi-function(table)
 */

Back to top page