// program that inputs a positive integer and outputs its Mobius function.
// The program  implements the following two functions (other than the main):
// 	1. int square_free(int n): returns 1 if n is square_free, 0 otherwise
// 	2. int mobius(int n): returns the mobius function of n
// author:rahule@cse.iitk.ac.in

#include<stdio.h>

int square_free(int);	// returns 1 if n is square_free, 0 otherwise
int mobius(int);	// returns the mobius function of n
main()
{
  int n,mob;
  printf("Enter the number  :");
  scanf("%d",&n);
  mob=mobius(n);	//caculates mobius function
  printf("\nThe mobius number of %d is %d",n,mob);
}

int mobius(int n)
// returns the mobius function of n
{
  int cnt=0,i,j;
  if(!square_free(n))	//if n is not square free,then returns 0
    return(0);
  else		//if n is square free
  {
    for(i=2;i<=n;i++)		 //calculates the number of prime factors
    {
      if(n%i==0)	//if i is a factor of n,then check whether i is prime or not
      {
	for(j=2;j<=i/2;j++)	//loop to check whether i is prime or not
	{
	  if(i%j==0)
	    break;
	}
	if(j>i/2)	//ie,when the loop exits,if the j value is greatr than i/2,that implies "break" was not executed.ie,it has no factors.ie,it is prime
	cnt++;		// increament the count of prime 
      }
    }
    if(cnt%2==0)	//if total count of prime is even,return 1	
      return(1);
    else
      return(-1);	//if total count is odd,returm -1
  }
}

int square_free(int n)
// returns 1 if n is square_free, 0 otherwise
{
    int i;
    for(i=2;i<=n;i++)
    {
      if((i*i)>n)
	break;
      if(n % (i*i) == 0)	//if i*i is a factor of n,then n is not square free.So return 0
	return(0);
    }
    return(1);	//there was no i such that i*i was a factor of n.So,n is square free.return 1
}