欧拉函数(Euler)

对正整数 n，欧拉函数是小于等于 n 的正整数中与 n 互质的数的数目

1. 求出 n 的素因子集合$a_1, a_2,..., a_n$
2. $ans = n \times (1 - \frac{1}{a_1}) \times (1 - \frac{1}{a_2}) ... \times (1 - \frac{1}{a_n})$

核心代码

export function phi(n: number) {
    let ans = n;
    for (let i = 2; i ** 2 <= n; i++) {
        // 求出n的素因子
        if (n % i === 0) ans = (ans / i) * (i - 1);
        while (n % i === 0) n /= i;
    }
    if (n !== 1) ans = (ans / n) * (n - 1);
    return ans;
}