学习笔记：求解欧拉函数

什么是欧拉函数？

\varphi(n)

表示小于等于

n

的正整数中，与

n

互质的数的个数。记作：

\varphi(n) = | \{ 1 \le k \le n | \gcd(k,n) = 1 \} |

如何求解？

1.若 $n$ 为质数：

\varphi(n) = n - 1

2.若 $n = p^k$ ， $p$ 为质数：

\varphi(p^k) = p^k - p^{k - 1} = p^k \left( 1 - \frac{1}{p} \right)

3.若 $n = a \times b,\gcd(a,b) = 1$ ：

\varphi(ab) = \varphi(a)\varphi(b)

4.通项公式：

对于任意正整数

n

，其质因数分解为：

n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}

则：

\varphi(n) = n \times \left(1 - \frac{1}{p_1} \right) \times \left(1 - \frac{1}{p_2} \right) \times \cdots \times \left(1 - \frac{1}{p_m} \right) = n \prod_{i = 1}^m \left(1 - \frac{1}{p_i} \right)

关于代码实现

我们注意到通项公式中有一个分数：

\frac{1}{p_i}

。在数论中，我们需要让所有数尽可能为整数。而在

\texttt{C++}

环境中，

\frac{1}{p_i}

这个分数在整数下一定为

0

。

所以，我们需要改造这个式子。换句话说，我们需要避免精度问题。

我们先将通项公式转化成伪代码语言：

CPP

res <- n 
for i = 2 to sqrt n:
    if (i 为质数且 i|n)
        res <- res * (1 - 1 / i);

重点就在这个式子：

res \gets res * (1 - 1 \ / \ i)

去括号，得：

res \gets res - res \ / \ i

将

res \ / \ i

提出来，得

res \gets res \ / \ i \times (i - 1)

这个式子不会出现精度问题。

为什么

res \ / \ i

不会出现精度问题呢？

因为

i

是

n

的质因子，那么必然有

i \mid res

。

这样代码就好写了。

学习笔记：求解欧拉函数

文章操作

什么是欧拉函数？

如何求解？

1.若 $n$ 为质数：

2.若 $n = p^k$ ， $p$ 为质数：

3.若 $n = a \times b,\gcd(a,b) = 1$ ：

4.通项公式：

关于代码实现

相关推荐

评论

学习笔记：求解欧拉函数

文章操作

什么是欧拉函数？

如何求解？

1.若 nnn 为质数：

2.若 n=pkn = p^kn=pk，ppp为质数：

3.若 n=a×b,gcd⁡(a,b)=1n = a \times b,\gcd(a,b) = 1n=a×b,gcd(a,b)=1：

4.通项公式：

关于代码实现

相关推荐

评论

1.若 $n$ 为质数：

2.若 $n = p^k$ ， $p$ 为质数：

3.若 $n = a \times b,\gcd(a,b) = 1$ ：