How many positive integers less than n are relatively prime to n?

Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0

        such that a = xy and b = xz.

 #include<stdio.h>
#include<math.h>


#define N 31650
#define p 5000


bool flag[N];
int prime[p];


void seive()
{
int i,j,k,r,c=0;
k=sqrt(N);
flag[1]=true;
prime[++c]=2;
for(i=3;i<=N;i+=2)
{
if(flag[i]==false)
{
prime[++c]=i;


if(i<=k)
{
r=i+i;
for(j=i*i;j<=N;j+=r)
flag[j]=true;
}
}
}
}
int phi(int x)
{
int i,r=1,k,j,l,m;
k=sqrt(x);


for(i=1;prime[i]<=k;i++)
{
for(j=0,l=1,m=1;x%prime[i]==0;j++)
{
x/=prime[i];
m*=prime[i];
if(j)
l*=prime[i];
}
k=sqrt(x);
if(j)
r*=m-l;
}
if(x>1)
r*=x-1;
return r;
}


int main()
{
seive();
int n;
while(scanf("%d",&n)==1 && n)
{
if(n>1)
printf("%d\n",phi(n));
else
printf("0\n");


}
return 0;
}