欧拉函数在 C 语言中的高效实现167

欧拉函数（也称为 φ 函数）对于解决密码学、数论和组合学中的问题至关重要。欧拉函数 φ(n) 给出了小于或等于 n 的正整数中与 n 互质的数的个数。在 C 语言中，可以通过利用以下算法高效地计算欧拉函数：

算法步骤：
从 1 到 n 创建一个数组，初始化所有元素为 1。
对于每个 i 从 2 到 n 的平方根：

如果 i 是 n 的因子，则对于每个 j = i2 到 n，将 φ(j) 更新为 φ(j) * (1 - 1/i)。


对于每个 i 从 n 的平方根 + 1 到 n：

如果 i 是 n 的因子，则 φ(i) 更新为 φ(i) * (1 - 1/i)。

时间复杂度：

该算法的时间复杂度为 O(n * log(log(n)))，其中 n 是欧拉函数要计算的数字。

C 语言实现：```c
#include
#include
long long phi(long long n) {
long long *phi_array = (long long*)malloc((n + 1) * sizeof(long long));
for (long long i = 1; i

2024-11-16

上一篇：C 语言函数手册：权威参考指南

下一篇：在 C 语言中轻松输出英文引号