欧拉函数

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代码模板


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)$