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 > , y > , z > such that a = xy and b = xz.
Input
There are several test cases. For each test case, standard input contains a line with n <= ,,,. A line containing follows the last case.
Output
For each test case there should be single line of output answering the question posed above.
Sample Input
Sample Output
Source
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define ll long long
ll eular(ll n){
ll ans=;
for(ll i=;i*i<=n;i++){
if(n%i==){
ans*=i-,n/=i;
while(n%i==){
ans*=i;
n/=i;
}
}
}
if(n>) ans*=n-;
return ans;
}
int main()
{
ll n;
while(scanf("%I64d",&n)==){
if(n==) break;
ll ans=eular(n);
printf("%I64d\n",ans);
}
return ;
}