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

• View this file on GitHub
• Last update: 2024-02-19 12:20:55+09:00
• Include: #include "C++/math/phitable.hpp"

Verified with

• test/phi_table.test.cpp

Code

#pragma once

#include <vector>
#include <numeric>
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(int i = 2; i <= n; ++i) {
			if(euler[i] == i) {
				for(int j = i; j <= n; j += i) {
					euler[j] = euler[j] / i * (i - 1);
				}
			}
		}
	}
	std::vector<int> get() const { return euler; }
};

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

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

#include <vector>
#include <numeric>
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(int i = 2; i <= n; ++i) {
			if(euler[i] == i) {
				for(int j = i; j <= n; j += i) {
					euler[j] = euler[j] / i * (i - 1);
				}
			}
		}
	}
	std::vector<int> get() const { return euler; }
};

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

Back to top page