欧拉函数求解

发布于:2021-11-30 17:32:29

?


通式:



其中p1, p2……pn为x的所有质因数,x是不为0的整数。


φ(1)=1(和1互质的数(小于等于1)就是1本身)。


注意:每种质因数只一个。 比如12=2*2*3那么φ(12)=φ(4*3)=φ(2^2*3^1)=(2^2-2^1)*(3^1-3^0)=4


若n是质数p的k次幂,



,因为除了p的倍数外,其他数都跟n互质。


设n为正整数,以 φ(n)表示不超过n且与n互素的正整数的个数,称为n的欧拉函数值


φ:N→N,n→φ(n)称为欧拉函数。


欧拉函数是积性函数??若m,n互质,



特殊性质:当n为奇质数时,



, 证明与上述类似。


若n为质数则



#include
using namespace std;
//直接求欧拉函数的值
int euler(int n)
{
int rea=n;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)//第一次找到 的必为素因子
{
rea=rea-rea/i;//同一个素因子只能用一次
while(n%i==0)
{
n/=i;//把该素因子全部去掉
}
}
}
if(n>1)
rea=rea-rea/n;
return rea;
}
int main()
{
int n;
cin>>n;
cout< return 0;
}

先处理素数,再求解


#include
using namespace std;
bool is_prime[100];
int p[100];
void check()
{
for(int i=2;i<100;++i){
is_prime[i]=1;
}
for(int i=2;i*i<100;++i)
{
if(is_prime[i]){
for(int j=i*i;j<100;j +=i)
{
is_prime[j]=0;
}
}
}
int k=0;
for(int i=2;i<=100;i++)
{
if(is_prime[i])
{
p[k++]=i;
}
}

}
int main() {
check();
int n;
cin>>n;
int res=n;
for(int k=0;p[k]*p[k]<=n;k++)
{
if(n%p[k]==0)
{
res=res-res/p[k];
}
while(n%p[k]==0)
{
n/=p[k];
}
}
if(n>1)
{
res=res-res/n;
}
cout< return 0;
}

?


?

相关推荐

最新更新

猜你喜欢