Толевая функция Эйлера в C

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

Функция Эйлера подсчитывает положительные целые числа до заданного целого числа п, которые взаимно просты с п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)

1 1 
2 1 
3 2 
4 2 
5 4 
6 2 
7 6 
8 4 
9 6