首页 > 代码库 > 找新朋友（欧拉函数）
找新朋友（欧拉函数）
在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler‘s totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。
简介:
φ函数的值
φ(1)=1（唯一和1互质的数就是1本身）。
若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
特殊性质：当n为奇数时，φ(2n)=φ(n), 证明于上述类似。
欧拉函数的编程实现：
利用欧拉函数和它本身不同质因数的关系，用筛法计算出某个范围内所有数的欧拉函数值。
欧拉函数和它本身不同质因数的关系：欧拉函数ψ（Ｎ）＝Ｎ｛∏ｐ｜Ｎ｝（１－１/ｐ）。（Ｐ是数Ｎ的质因数）
如：
ψ（１０）＝１０×（１－１/２）×（１－１/５）＝４；
ψ（３０）＝３０×（１－１/２）×（１－１/３）×（１－１/５）＝８；
ψ（４９）＝４９×（１－１/７）＝４２。
题目：
Input第一行是测试数据的组数CN（Case number，1<CN<10000），接着有CN行正整数N（1<n<32768），表示会员人数。Output对于每一个N，输出一行新朋友的人数，这样共有CN行输出。
Sample Input
2
25608
24027
Sample Output
7680
16016
注意：在变成实现欧拉函数的时候，算式n*(1-1/p)要写成(n-n/p)，减小误差，不然最终结果不对！！！
AC代码：
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int a[100];
bool is_prime(int n)
{
for (int i=2;i<=sqrt(n);i++)
if (n%i==0)
return 0;
return 1;
}
int main()
{
int t,n;
cin>>t;
while (t--)
{
memset(a,0,sizeof(a));
cin>>n;
int sum=n;
for (int i=2;i<=n;i++)
{
if (n%i==0&&is_prime(i))
sum=sum-sum/i;
}
cout << sum << endl;
}
return 0;
}
is_prime()判断是否为素数；
找新朋友（欧拉函数）