Eratostene3

#include <fstream>
#define N 1000001
using namespace std;

int Phi(int n)
{
    int d;
    unsigned long long int nrp=n,prod=1;
    if(n%2==0)
    {
        while(n%2==0)
            n/=2;
        nrp*=(2-1),prod*=2;
    }
    d=3;
    while(n>1)
    {
        if(n%d==0)
        {
            while(n%d==0)
                n/=d;
            nrp*=d-1,prod*=d;
        }
        else
            d+=2;
        if(n>1&&d*d>n)
        {
            nrp*=n-1,prod*=n;
            break;
        }
    }
    return (int) (nrp/prod);
}

int main()
{
    int n;
    ifstream f("eratostene3.in");
    f>>n;
    int x;
    ofstream g("eratostene3.out");
	while(n--)
        f>>x,g<<Phi(x)<<' ';
	return 0;
}