欧拉在 C 中的 totient 函数

Question

对于自然数n，欧拉总函数定义为集合{1,...n}中与n互质的自然数的个数。我必须用 C 语言编写一个程序，以便输入 n 输出是 n 的欧拉总函数。这是我的尝试：

#include<stdio.h> 
int main(void) {

int n,k;

scanf("%d", &n);

for (k=1; k<n; k++) {
  if(n%k !=0) 

  printf("%d\n", k);

  }

return 0;

}

后来我意识到这也应该给我 1 作为每个 n 的输出，所以我想我可以在 return 0 之前添加这个：

if(k=1) printf("1");

但这看起来不太好...我怎样才能更智能地编写这个程序？

Answer 1

Euler 的 totient 函数计算给定整数 n 内与 n 互质的正整数 link

您可以计算相对质数或互质数，如下所示：

int coprime(int a, int b)
{
    while(b)
    {
        a %= b;

        //swap a & b
        int temp = a;
        a = b;
        b = temp;
    }

    return a;
}

计算欧拉的 Totient 为：

int phi(int n)
{
    int result = 0;
    int k;
    for(k = 1; k <= n; k++)
        result += coprime(k, n) == 1;
    return result;
}

测试：

int main()
{
    int i;
    for(i = 1; i < 10; i++)
        printf("%d %d\n", i, phi(i));
    return 0;
}

结果（与other结果比较）

欧拉在 C 中的 totient 函数

Euler's totient function in C

c

primes

loops