用c编成实现计算欧拉函数数值的算法

#include <stdio.h>

int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}

int euler(int n) {
int result = 1;
for (int i = 2; i < n; i++) {
if (gcd(i, n) == 1) {
result++;
}
}
return result;
}

int main() {
int n;
printf("Enter a positive integer: ");
scanf("%d", &n);
printf("Euler's totient function of %d is %d", n, euler(n));
return 0;
}

相关问题

编成实现计算欧拉函数值的c语言算法。

以下是一种基于欧拉定理的算法，可以计算欧拉函数值：

#include <stdio.h>

int euler(int n) {
    int result = n; // 初始化结果为 n
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) { // i 是 n 的一个质因数
            result = result / i * (i - 1); // 根据欧拉定理计算结果
            while (n % i == 0) {
                n /= i; // 去除 i 的所有因子
            }
        }
    }
    if (n > 1) { // n 是一个大于 sqrt(n) 的质数
        result = result / n * (n - 1); // 根据欧拉定理计算结果
    }
    return result;
}

int main() {
    int n;
    printf("请输入一个正整数 n：");
    scanf("%d", &n);
    printf("phi(%d) = %d\n", n, euler(n));
    return 0;
}

算法思路：

1. 初始化结果为 n。

2. 从 2 开始枚举所有小于等于 sqrt(n) 的质数 i，如果 n 能被 i 整除，则 i 是 n 的一个质因数。

3. 根据欧拉定理，当 n 能被 i 整除时，phi(n) = phi(n / i) * (i - 1) / i。

4. 去除 n 中所有 i 的因子。

5. 如果 n 仍然大于 1，则说明 n 是一个大于 sqrt(n) 的质数，根据欧拉定理，phi(n) = n - 1。

6. 返回结果。

例如，输入 n = 12，程序输出 phi(12) = 4，说明 12 以内有 4 个与 12 互质的正整数。这 4 个数分别是 1、5、7、11。

用C语言编程实现计算欧拉函数值的算法

#include <stdio.h>

int euler(int n) {
int result = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
result = result / i * (i - 1);
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) {
result = result / n * (n - 1);
}
return result;
}

int main() {
int n;
printf("请输入一个正整数:");
scanf("%d", &n);
printf("欧拉函数值为:%d\n", euler(n));
return 0;
}