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

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

Required by

• Tetration(a↑↑b) (C++/math/tetration.hpp)

Verified with

• test/phi.test.cpp
• test/tetration.test.cpp

Code

#pragma once
template <class T> inline T euler_phi(T n) {
	T res = n;
	for(T i = 2; i * i <= n; ++i) {
	    if(n % i == 0) {
			res -= res / i;
			while(n % i == 0) {
				n /= i;
			}
		}
	}
	if(n > 1) {
		res -= res / n;
	}
	return res;
}

/**
 * @brief Euler's Phi-function
 */

#line 2 "C++/math/euler_phi.hpp"
template <class T> inline T euler_phi(T n) {
	T res = n;
	for(T i = 2; i * i <= n; ++i) {
	    if(n % i == 0) {
			res -= res / i;
			while(n % i == 0) {
				n /= i;
			}
		}
	}
	if(n > 1) {
		res -= res / n;
	}
	return res;
}

/**
 * @brief Euler's Phi-function
 */

Back to top page