Implementation of Euler's Totient @description Euler Totient Function is also known as phi function. More...
Implementation of Euler's Totient @description Euler Totient Function is also known as phi function.
\[\phi(n) = \phi\left({p_1}^{a_1}\right)\cdot\phi\left({p_2}^{a_2}\right)\ldots\]
where \(p_1\), \(p_2\), \(\ldots\) are prime factors of n.
3 Euler's properties:
Applying this 3 properties on the first equation.
\[\phi(n) = n\cdot\left(1-\frac{1}{p_1}\right)\cdot\left(1-\frac{1}{p_2}\right)\cdots\]
where \(p_1\), \(p_2\)... are prime factors. Hence Implementation in \(O\left(\sqrt{n}\right)\).
Some known values are:
Definition in file eulers_totient_function.cpp.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4