// program that takes a positive integer as input and calculates its
// totient number. program  implements the following two functions
// (other than the main): 
// 	1. int coprime(int m, int n): returns 1 if m and n are co-prime, 0 otherwise
// 	2. int totient(int n): returns the totient number of n
// 
// The totient number T(n) of a positive integer n is defined to be the number of
// positive integers less than or equal to n that are coprime to n 

//Author:rahule@cse.iitk.ac.in

#include<stdio.h>
int coprime(int , int );		//returns 1 if m and n are co-prime, 0 otherwise
int totient(int );			//returns the totient number of n
main()
{
  int num,t;
  printf("Enter the number :");
  scanf("%d",&num);
  t=totient(num);		//calculates the totient number of num
  printf("the totient number of %d is %d\n",num,t);
}

int totient(int n)
//function to calculate the totient
{
  int t=1,i;
  if(n==1)	//special case:if n is 1,the return 1
    return(t);
  else
  {
    for(i=2;i<=n;i++)
    {
      if(coprime(i,n))		//calculates howmany numbers are there less than 'n' and co-prime to 'n'
	t++;
    }
    return(t);
  }
}

int coprime(int m, int n)
//function to check whether m and n are co-prime to each other
{
  int min,i;
  if(m>n)		//calculates the minimum of m and n
    min=n;
  else
    min=m;
  
  for(i=2;i<=min;i++)		//checks whether m and n has any common factors or not
  {
    if((m%i==0)&&(n%i==0))	//if m and n has a commmon factor,then return 0,ie they are not co-prime to each other	
      return(0);
  }
  return(1);		//if the execution reaches here,that means no common factors was found.ie,m and n are co-prime..so return 1
}