UVA - 10179 - Irreducable Basic Function

Problem Link: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1120

Explanation: Just use Euler's Phi function, also known as the totient function, is a function that, for a given positive integer , calculates the number of positive integers smaller than or equal to  that are relatively prime to . (Note that except when , only integers strictly smaller than  are counted, because .)

Code First Then See Solution


Code: 

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll phi(ll n)
{
    ll res=n;
    if(res%2==0)
    {
        while(res%2==0)
        {
            res/=2;
        }
        n-=n/2;
    }
    for(ll i=3;i*i<=res;i+=2)
    {
        if(res%i==0)
        {
            while(res%i==0)
                res/=i;
            n-=n/i;
        }
    }
    if(res>1)
        n-=n/res;
    return n;
}


int main()
{
   long long n;
   while(cin>>n)
   {
       if(n==0)
        break;
       ll ans=phi(n);
       cout<<ans<<endl;
   }
   return 0;
}