欧拉函数、筛法求欧拉函数

欧拉函数、筛法求欧拉函数

目录

前言

1.求欧拉函数

2.筛法求欧拉函数

---

前言

        在数论，对正整数n，欧拉函数varphi(n)是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。

例如varphi(8)=4，因为1,3,5,7均和8互质（当a与b只有1的公因数的时候，就将a和b称为互质）。

从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。

1.求欧拉函数

对于一个数n

如果n是质数，那么它的欧拉函数就为n-1;

如果n不是质数，那么n一定能被分解为质数相乘的形式。在1~n中与n互质的数，一定不包含n的任一质数。那么只要从1~n中，剔除所有n的质数的倍数，剩下的就是与n互质的数。

例如 n=30，6=2*3*5；

剔除1~30中2的倍数：30/2=15，要剔除15个

剔除1~30中3的倍数：30/3=10，要剔除10个

剔除1~30中5的倍数：30/5=6，要剔除6个

但是，在这里我们不难看出有重复剔除的数。例如2和3的倍数（6、12、36.....）、2和5的倍数、3和5的倍数 被重复剔除了一次，2、3和5的倍数被重复剔除了2次。

根据容斥原理，我们要去除重复剔除的个数。

所以在n-30/2-30/3-30/5的基础上，去除重复的。

得到：n-30/2-30/3-30/5+30/(2*3)+30/(2*5)+30/(3*5)-30/(2*3*5)

最后的-30/(2*3*5)是因为+30/(2*3)+30/(2*5)+30/(3*5)添加了3次2、3和5的倍数。

整理这个公式就可得到

n-30/2-30/3-30/5+30/(2*3)+30/(2*5)+30/(3*5)-30/(2*3*5)  ==>  n(1-1/2)(1-1/3)(1-1/5)

推导过程：

其中pi为质数

berTheory;import java.util.Scanner;/*** @Auther: duanYL* @Date: 2023/10/31/14:13* @Description:*/
public class EulerFunction {public static void main(String[] args) {}public static int phi(int n) {int res = n;for (int i = 2; i <= n/i; i++) {if (n % i == 0) {res = res / i * (i - 1);    //先除防止溢出while (n % i == 0)n /= i;}}if (n>1)res = res / n * (n - 1);return res;}
}

2.筛法求欧拉函数

题目：给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。

假设当前有一个数为x，x属于1~n。

如果x为质数，那么他的互质数的个数就为x-1,phi(x)=x-1;

如果x是合数，x必定能分解为一个质数p乘以一个数n，要求phi(x)就有以下两种情况：

1.质数p是n的因数，那么phi(x) = phi(n)*p        (根据求phi的公式得出的)

2.质数p不是n的因数，那么phi(x) = phi(n) * p*(1-1/p) = phi(n) * (p-1)         (根据求phi的公式得出的)

public static int[] getAllEuler(int n) {int primes[] = new int[n + 1];int euler[] = new int[n + 1];boolean st[] = new boolean[n + 1];int cnt = 0;euler[1]=1;for (int i = 2; i <= n; i++) {if (!st[i]) {euler[i] = i - 1;primes[cnt++] = i;}for (int j = 0; primes[j] <= n / i; j++) {int t = primes[j] * i;st[t] = true;if (i % primes[j] == 0) {euler[t]=euler[i]*primes[j];break;}euler[t] = euler[i]*(primes[j]-1);}}return euler;
}