euler phi gfg

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