欧拉函数求法
大家好，又见面了，我是你们的朋友全栈君。
欧拉函数是计算在1-n中n的质因数的个数；
φ（x）=x*(p1-1)/p1*(p2-1)/p2*(p3-1)/p3…*(pn-1)/pn 其中p1,p2,p3…是x的质因数；
若x是质数: φ(x)=x-1 若x是质数p的k次幂(即x=p^k)：φ(x)=p^k-p^(k-1)=(p-1)p^(k-1)
积性： φ(n*m)=φ(n)*φ(m) 其中m、n互质。
具体的证明和其他介绍就不多说了=.= 下面开始介绍算法。
暴力求一个欧拉值 嗯，没错很暴力。 用公式：φ（x）=x*(p1-1)/p1*(p2-1)/p2*(p3-1)/p3…*(pn-1)/pn 暴力枚举质因数，不具体说了，看代码喽：
int euler(int x){
int res=x;
for(int i=2;i*i<=x;++i){
if(x%i==0){
res=res/i*(i-1);
while(x%i==0) x/=i;
}
}
if(x>1) res=res/x*(x-1);
return res;
}打欧拉函数表： 类似于筛法~~~~ 所以可以先学习一下筛法=.=
方法一： 类似于埃氏筛？ 初始化phi[i]=i； 循环范围内的所有数x； 如果x是质数，将x的倍数乘1-1/x；
原理：φ（x）=x*(p1-1)/p1*(p2-1)/p2*(p3-1)/p3…*(pn-1)/pn（还是它~~~）
void euler()
{
for(int i=1;i<=n;i++)phi[i]=i;
for(int i=2;i<=n;i++)
if(phi[i]==i)
for(int j=i;j<=n;j+=i)
phi[j]=phi[j]/i*(i-1);//防爆先除后乘；
}方法二： 类似于线性筛？
遍历1-n所有数x； 如果x是质数（m[x]为处理）那么更新phi[x]，p[++tot]，m[x]值；
对于每一个i用它去乘质数表第j项=k，更新m[k]； 原理同线性筛：每一个合数只会被他的最小质因数筛去；
如果m[i]==p[j]，更新phi[k]=phi[i]*p[j]break（保证不重复筛某个数）； 正确性证明： phi[i]=i*(p1-1)/p1*(p2-1)/p2*…*(pn-1)/pn phi[k]=k*(p1-1)/p1*(p2-1)/p2*…*(pn-1)/pn=phi[i]*p[j]（k=p[j]*i） p[j]==m[i]所以p[j]==p1,p[j]-1/p[j]已经包含在phi[i]里;
原理： 1、φ（x）=x*(p1-1)/p1*(p2-1)/p2*(p3-1)/p3…*(pn-1)/pn； 2、若x是质数: φ(x)=x-1。
上代码~：
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 100000000
using namespace std;
int n,tot,p[maxn],m[maxn],phi[maxn];//p-->质数，m-->i的最小质因数，phi-->欧拉值
void euler()
{
phi[1]=1;
tot=0;
int k;
for(int i=2;i<=n;++i)
{
if(!m[i])//i是质数
{
p[tot++]=m[i]=i;//i加入质数表，更新i的最小质因数为i
phi[i]=i-1;//i的欧拉函数值
}
for(int j=0;j<tot&&(k=p[j]*i)<=n;j++)
{
m[k]=p[j];//线性筛的性质，每个合数会被他的最小质因数找到
if(m[i]==p[j])//i的最小质因数为质数表第j项
{
phi[k]=phi[i]*p[j];//phi[i]=i*(p1-1)/p1*(p2-1)/p2*...*(pn-1)/pn而p[j]==m[i]所以p[j]==p1,p[j]-1/p[j]已经包含在phi[i]里;phi[k]=k*(p1-1)/p1*(p2-1)/p2*...*(pn-1)/pn=phi[i]*p[j]（k=p[j]*i）
break;//防止重复计算，每个i只由m[i]更新
}
else phi[k]=phi[i]*(p[j]-1);
}
}
}
int main()
{
n=100000000;
euler();
// for(int i=1;i<=n;i++)
// printf("%d %d \n",i,phi[i]);
}实测：线性筛还是会比埃氏筛快一xu点duo； 跑100000000的欧拉表，线性筛比埃氏筛快0.8-1s~
感谢spli大神教我~ –> 膜一膜spli大神
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/172057.html原文链接：https://javaforall.cn
腾讯云开发者
