eulers_totient_function.cpp File Reference

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

#include <cassert>
#include <cstdint>
#include <iostream>

Include dependency graph for eulers_totient_function.cpp:

Go to the source code of this file.

Namespaces
namespace	math
	for assert

Functions
uint64_t	math::phiFunction (uint64_t n)
	Function to calculate Euler's Totient.
static void	test ()
	Self-test implementations.
int	main ()
	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

Definition in file eulers_totient_function.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 77 of file eulers_totient_function.cpp.

           {
    test();
    return 0;
}

test()

void test ( )

static

Self-test implementations.

Returns

void

Definition at line 61 of file eulers_totient_function.cpp.

                   {
    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";
}