eulers_totient_function.cpp File Reference

C++ Program to find Euler's Totient function. More...

#include <cstdlib>
#include <iostream>

Include dependency graph for eulers_totient_function.cpp:

Functions
uint64_t	phiFunction (uint64_t n)
int	main (int argc, char *argv[])
	Main function. More...

Detailed Description

C++ Program to find Euler's Totient function.

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:

1. \(\phi(n) = n-1\)
2. \(\phi(n^k) = n^k - n^{k-1}\)
3. \(\phi(a,b) = \phi(a)\cdot\phi(b)\) where a and b are relative primes.

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:

• \(\phi(100) = 40\)
• \(\phi(1) = 1\)
• \(\phi(17501) = 15120\)
• \(\phi(1420) = 560\)

Function Documentation

main()

int main	(	int	argc,
		char *	argv[]
	)

Main function.

                                 {
    uint64_t n;
    if (argc < 2) {
        std::cout << "Enter the number: ";
    } else {
        n = strtoull(argv[1], nullptr, 10);
    }
    std::cin >> n;
    std::cout << phiFunction(n);
    return 0;
}

Here is the call graph for this function:

phiFunction()

uint64_t phiFunction

(

uint64_t

n

)

Function to caculate Euler's totient phi

                                 {
    uint64_t result = n;
    for (uint64_t i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}