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.
给定n，一个正整数，有多少小于n的正整数相对n是素数？如果没有整数x>1，y>0，z>0，使得a=xy和b=xz，则两个整数a和b是相对素的。
输入
有几个测试用例。对于每个测试用例，标准输入包含一行n<=100000000。最后一个大小写后面是包含0的行。
输出
对于每个测试用例，应该有一行输出来回答上面提出的问题。
Sample Input
7
12
0
Sample Output
6
4
欧拉函数模板题，不过这道题要注意数据范围是long long。
#include <string.h>//字符串操作cccccccccc函数 #include <stdio.h>//C的输入输出 #include <math.h>//C中的数学函数 #include <queue>// STL queue #include<iostream> #include<set> #include<map> #include<vector> #include <ctime> #include <stack>//sTL stack #include <algorithm> #include<string>//这个是string的头文件 using namespace std; //const double PI = acos(-1.0); const int maxn = 1e6+5; const double eps = 1e-6; const int INF = 0x3f3f3f3f;//无穷大 typedef long long ll;//以后出现的ll为long long 类型 int Ss=8; #define M(a,x) memset(a,x,sizeof(a)) #define AU(i,x,y) for(llt i=x;i<=y;i++) ll euler(ll n) { ll ans=n; for(int i=2;i*i<=n;++i){ if(n%i==0){ ans-=ans/i; while(n%i==0) n/=i; } } if(n>1) ans-=ans/n; return ans; } int main() { ll n; while(~scanf("%lld",&n)&&n) { if(n==1) printf("0\n"); else printf("%lld\n",euler(n)); } return 0; }
