1// C program to calculate Euler's Totient Function
2#include <stdio.h>
3
4int phi(int n)
5{
6 int result = n; // Initialize result as n
7
8 // Consider all prime factors of n and subtract their
9 // multiples from result
10 for (int p = 2; p * p <= n; ++p) {
11
12 // Check if p is a prime factor.
13 if (n % p == 0) {
14
15 // If yes, then update n and result
16 while (n % p == 0)
17 n /= p;
18 result -= result / p;
19 }
20 }
21
22 // If n has a prime factor greater than sqrt(n)
23 // (There can be at-most one such prime factor)
24 if (n > 1)
25 result -= result / n;
26 return result;
27}
28
29// Driver program to test above function
30int main()
31{
32 int n;
33 for (n = 1; n <= 10; n++)
34 printf("phi(%d) = %d\n", n, phi(n));
35 return 0;
36}
37