Relatives Prime uva

#include<bits/stdc++.h>
using namespace    std;
#define pb           push_back
#define mx           1000000009

typedef long long int       ll;

ll ans = 0;
vector<ll>prime;
bool vis[mx+2];  //mx is define in above of the code;
void sieve() {
    ll x=sqrt((int)mx);
    for(ll i=3; i<=x; i+=2) {
        if(vis[i]==0) {
            for(ll j=i*i; j<mx; j+=2*i)
                vis[j]=1;
        }
    }
    prime.pb(2);
    for(ll i=3; i<mx; i+=2)
        if(vis[i]==0)
            prime.pb(i);
}

vector<int>FactorList;

void PrimeFactorize( ll n)
{

    for(ll i=0; prime[i]*prime[i]<=n; i++)
    {
        if(n%prime[i]==0)
        {
            while(n%prime[i]==0) n/=prime[i];
          //  FactorList.pb(prime[i]);
            ans = ans-ans/prime[i];
        }
    }
    if(n>1) ans = ans-ans/n;
}

int main()
{
        ssieve();
       ll n;
        while(scanf("%lld",&n)==1)
        {
            ans = n;
            if(n==0)return 0;
            PrimeFactorize(n);
           // for(int i=0; i<FactorList.size(); i++)
           // {
           //      //cout<<ans<<" "<<ans/FactorList[i]<<endl;
           //      ans = ans-(ans/FactorList[i]);

           // }
           printf("%lld\n",ans);
           // cout<<"Prime List: "<<endl;
           // for(int i=0; i<FactorList.size(); i++) cout<<FactorList[i]<<" ";
            ans = 0;
        }
    return 0;
}