欧拉函数

1 欧拉函数的定义

欧拉函数（Euler’s totient function），通常记为φ(n)，是一个与正整数n相关的数论函数。它表示小于或等于n的正整数中与n互质的数的个数。互质的意思是这些数的最大公约数（最大公因数）为1。

欧拉函数的计算公式是$φ(n) = n \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \ldots \times \left(1 - \frac{1}{p_k}\right)$其中，n可以分解为素数因子的乘积：$n = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}$其中，p1、p2、…、pk是不同的素数，$a1、a2、…、ak$是它们的幂次。

举个例子，如果n = 12，那么它可以分解为2^2 * 3^1。因此，φ(12) = 12 * (1 - 1/2) * (1 - 1/3) = 4。

欧拉函数在数论和密码学中有广泛的应用，例如在RSA算法中，欧拉函数的计算用于生成加密密钥和解密密钥。

Java代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import java.util.Scanner;

public class 欧拉函数 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc= new Scanner(System.in);
		int n = sc.nextInt();
		System.out.println(phi(n));
		System.out.println(phii(n));
	}
	
	public static int phi(int x) {
		int res=x;
		for(int i = 2;i<=x/i;++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;
	}
	
	
	public static long phii(long x) {
		long res =x;
		for(long i = 2;i<=Math.sqrt(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;
	}

}

欧拉代码公式推导

已知欧拉函数的计算公式是$φ(n) = n \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \ldots \times \left(1 - \frac{1}{p_k}\right)$

因为代码使用的迭代法一直循环进行相乘，所以我们用公式中$n\times (1-\frac{1}{p_1})$部分代说明。

代码中res相当于n,i相当于$p_1$，所以可得$res \times (1- \frac{1}{i})$

即:

$res \times(1-\frac{1}{i})$

$=res\times \frac{1}{i}(i-1)$

$=\frac{res}{i}\times(i-1)$

即代码部分res=res/i*(i-1)