Euler's Totient Function

Euler's Totient Function or phi-function,  phi(n). this function count the number of integer between 1 to n which are co-prime with n. 

co-prime mean : suppose we have two number x and y. then x and y will be co-prime when there gcd(x, y) = 1 that means x and y this two number have only common factor is 1. 

phi(12) = 4.  How it come 4???

Because, [ 2, 3, 4, 6, 8, 9, 10, 12 ] this eight number have factor with 12 is greater than 1.

Example : gcd(2, 12) = 2 

                  gcd(3, 12) = 3

                  gcd(4, 12) = 4   ......................

But [ 1, 5, 7, 11] only this four number have factor with 12 is equal to 1. So phi(12) = 4.

Now we that how can we calculate it by mathematically.

Suppose we have a positive number n. The prime factorization of n = P^x. 

So we write this,  phi(n) = phi(P^x).

phi(P^x) = P^x - Number of integers not coprime with P.

              = P^x - Number of multiple of P. ( if P is a prime number and x >= 1, then there are exactly P^x/P number between 1 to P^x that are divisible by P )

              = P^x - ( P^x / P )

              = ( P^x . ( P - 1 ) ) / P

              = ( P^x / P )  . (P - 1)

              = P^x-1 . ( P - 1 )

if p and q are relatively prime then we can write,

                                                       phi(pq) = phi(p) . phi(q)

Example : 12 = 2² . 3¹

Here 2 and 3 are prime factor of 12. 

So, phi(12) = phi(2²) . phi(3¹)

                   = 2^2-1 . (2-1) . 3^1-1 . (3-1)

                   = 4

That way, phi(12) = 4.

if n is prime number then,  phi(n) = n - 1.

#include<bits/stdc++.h>

#define N 1000006

#define ll long long int

using namespace std;

int p[N+1];

int phi[N+1];

void prime()

{

    p[0] = p[1] = 1;

    for(int i=2; i*i<=N; i++)

    {

        if(p[i] == 0)

        {

            for(int j=2; i*j<=N; j++)

                p[i*j] = 1;

        }

    }

}

void phifunction()

{

    for(int i=1; i<=N; i++)

        phi[i] = i;

    for(int i=2; i<=N; i++)

    {

        if(p[i] == 0)

        {

            for(int j=i; j<=N; j+=i)

                phi[j] = phi[j]/i*(i-1);

        }

    }

}

int main()

{

    prime();

    phifunction();

    ll i, n, m;

    cout << "Enter Two Number :: ";

    cin >> n >> m;

    cout << "\nphi-function value from " << n << " to " << m << " is :: \n";

    for(i=n; i<=m; i++)

        cout << i << " : " << phi[i] << endl;

    return 0;

}