eulers_totient_function.cpp File Reference

Implementation of Euler's Totient @description Euler Totient Function is also known as phi function. More...

#include <iostream>
#include <cassert>

Include dependency graph for eulers_totient_function.cpp:

Namespaces
namespace	math
	for IO operations

Functions
uint64_t	math::phiFunction (uint64_t n)
	Function to calculate Euler's Totient.
static void	test ()
	Self-test implementations.
int	main (int argc, char *argv[])
	Main function.

Detailed Description

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:

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\)

  Author

  Mann Mehta

Function Documentation

main()

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

Main function.

Parameters

argc	commandline argument count (ignored)
argv	commandline array of arguments (ignored)

Returns

0 on exit

                                 {
    test();
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Returns

void

                   {
    assert(math::phiFunction(1) == 1);
    assert(math::phiFunction(2) == 1);
    assert(math::phiFunction(10) == 4);
    assert(math::phiFunction(123456) == 41088);
    assert(math::phiFunction(808017424794) == 263582333856);
    assert(math::phiFunction(3141592) == 1570792);
    assert(math::phiFunction(27182818) == 12545904);
 
    std::cout << "All tests have successfully passed!\n";
}

Here is the call graph for this function: