euler_totient.cpp File Reference

Primary module interfact unit for module euler_totient. More...

#include <algorithm>
#include <numeric>
#include <vector>
import prime_decomposition;
import base;

Include dependency graph for euler_totient.cpp:

Functions
template<Integer T>
constexpr T	ntlib::euler_totient (const prime_factors< T > &factors) noexcept
	Computes Euler's totient function \(\phi(n)\) for a given number n.
template<Integer T>
constexpr T	ntlib::euler_totient (T n) noexcept
	Computes Euler's totient function \(\phi(n)\) for a given number.
template<Integer T>
std::vector< T >	ntlib::euler_totient_sieve (std::size_t N)
	Computes Euler's totient function \(\phi(n)\) for all integers up to a given number N.

Detailed Description

Primary module interfact unit for module euler_totient.

Function Documentation

euler_totient() [1/2]

template<Integer T>

T ntlib::euler_totient ( const prime_factors< T > & factors )

nodiscardconstexprexportnoexcept

Computes Euler's totient function \(\phi(n)\) for a given number n.

Template Parameters

T	An integer-like type.

Parameters

factors

The prime decomposition of n.

Returns

Euler's totient function \(\phi(n)\).

euler_totient() [2/2]

template<Integer T>

T ntlib::euler_totient ( T n )

nodiscardconstexprexportnoexcept

Computes Euler's totient function \(\phi(n)\) for a given number.

Template Parameters

T	An integer-like type.

Parameters

n	The given number.

Returns

Euler's totient function \(\phi(n)\).

euler_totient_sieve()

template<Integer T>

std::vector< T > ntlib::euler_totient_sieve ( std::size_t N )

nodiscardexport

Computes Euler's totient function \(\phi(n)\) for all integers up to a given number N.

Runtime: \(O(N \log(\log(N))\)

Template Parameters

T	An integer-like type.

Parameters

N	The number until which all values should be computed.

Returns

A std::vector<T> containing all values. The element at index 0 will be set to 0.