求小于n的数里，与n互为素数的个数
一.
奇数和偶数是否一定互素（排除1，不是比如6和9）；1和不和任意数互素(比如6采用欧拉定理验证下)。
若n已经进行唯一分解，直接欧拉公式。
如果n的标准素因子分解式是p1^a1*p2^a2*……*pm^am，其中众pj(j=1,2,……,m)都是素数，而且两两不等。则有 φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm) 利用容斥原理可以证明它。
二.不知唯一分解
1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 5 int main() 6 { 7 int n,i; 8 double sum; 9 while(scanf("%d",&n)&&n) 10 { 11 sum=n; 12 //还是运用了欧拉公式 13 if(n%2==0)//2也是素数 14 { 15 sum*=(double)(1 - 1.0/2);//为了突出关系写成了 (1 - 1.0/2) ,里面一定是1.0 16 while(n%2==0) 17 n/=2; 18 } 19 20 /*类似筛法的思想，已经去掉了2及其倍数，下面找奇因子，必须从小到大枚举， 21 3枚举到的话立马除尽3及其倍数防止再次枚举9（这样就不对了） 22 */ 23 for(i=3;n>1;i+=2) 24 { 25 if(n%i==0) 26 sum*=(1-(double)1/i); 27 while(n%i==0) 28 n/=i; 29 } 30 printf("%d\n",(int)sum); 31 } 32 //while(1); 33 return 0; 34 }
