UVa problem solution 10179 - Irreducable Basic Fractions

problem link

Discuss: in this problem you can assign n as result.then find the divisor of n. and subtract from the result. you will find the desired result

try yourself before see the code



#include<bits/stdc++.h>
using namespace std;
long long can=0;
int gcd(long long n)
{
   long long i;
   if(n==1)
    return n;
   if(n%2==0)
   {
       can-=can/2;
       while(n%2==0)
        n/=2;
   }
     for(i=3;i<=sqrt(n);i+=2)
     {
         if(n%i==0)
         {
               can-=can/i;;
        while(n%i==0)
            n/=i;
         }
     }
     if(n>1)
        can-=can/n;
    return can;
}
int main()
{

   long long n,i,j,cnt;
    while(cin >>n&&n)
    {
        cnt=0;
        can=n;
        gcd(n);
      cout <<can<<endl;
    }
    return 0;
}