Relatives

Relatives

TimeLimit: 1 Second   MemoryLimit: 32 Megabyte

Totalsubmit: 1566   Accepted: 513  

Description

Given n, a positive integer, 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.

Input

There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.

Output

For each test case there should be single line of output answering the question posed above.

Sample Input

7
12
0

Sample Output

6
4

考察欧拉函数

 若m=p1^e1*p2^e2.....pr^er

则从1到m与m互素的元素个数euler（m）=m*(1-1/p1)*(1-1/p2)*...*(1-1/pr)

#include<stdio.h>
#include<math.h>
long long int euler(long long int n)
{
long long int i,m = (int)sqrt(n+0.5),ans = n;
for(i = 2;i <= m;i++)
{
if(n%i==0)
ans = ans*(i-1)/i;
while(n%i==0)
n/=i;
}
if(n>1)
ans = ans*(n-1)/n;
return ans;
}
long long int a;
int main()
{
while(scanf("%lld",&a)!=-1&&a!=0)
{
printf("%lld ",euler(a));
}
return 0;
}