Star-Kevin

#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
typedef vector<ll> vi;

ll N;

vi primes;
vector<bool> bs(10000000);
ll __sieve_size;


void sieve(ll upperbound)
{
    __sieve_size = upperbound+1;
    fill(bs.begin(),bs.end(),false);

    bs[0] = bs[1] = 1;

    for(ll i = 2; i <= __sieve_size ; i++)
    {
        if(!bs[i])
        {
            for(ll j = i * i ; j <= __sieve_size ; j+=i)
            {
                bs[j] = 1;
            }
            primes.push_back(i);
        }
    }
}

bool isPrime(ll n)
{
    if(N <= __sieve_size) return bs[N];
    for(int i = 0; i < (int)primes.size();i++)
    {
        if( N % primes[i] == 0) return false;
    }
}

ll phi()
{

    ll result = N;   // Initialize result as n
    for (ll i= 0; primes[i]*primes[i] <= N; i++)
    {
        if (N % primes[i] == 0)
        {
            while (N % primes[i] == 0)
               N /= primes[i];
            result -= result / primes[i];

        }
    }
    if (N > 1)
        result -= result / N;
    return result;
}

long long totient(long long n) {
  if (n == 1) return 0;
  long long ans = n;
  for (int i = 0; primes[i] * primes[i] <= n; ++i) {
    if ((n % primes[i]) == 0) {
      while ((n % primes[i]) == 0) n /= primes[i];
      ans -= ans / primes[i];
    }
  }
  if (n > 1) {
    ans -= ans / n;
  }
  return ans;
}
int main()
{
    sieve(55000);
    while (cin >> N)
    {
        cout << ( phi() >> 1 ) << endl;
    }
}