Euler's_Totient_function.c

/*
Euler's totient function, also known as phi-function ϕ(n), counts the
numberof integers between 1 and n inclusive, which are coprime to n.
*/

#include <stdio.h>

int main(){
	int n;
	printf("Enter an integer: ");
	scanf("%d", &n);
	
	int temp=n;
	//This gives euler totient function for N
	// Time Complexity: O(N*root(N))
	int ans = n;
	for (int i = 2; i <= n; ++i) {
		if(n%i == 0){
			ans = ans - ans/i;
			while(n%i == 0)
				n/=i;
		}
	}
	if(n>1){
		ans = ans - ans/n;
	}
	n=temp;
	printf("\nThe euler totient function for %d is: %d",n,ans);

	//This gives euler totient function from 1 to N
	// Time Complexity: O(N loglogN) - same as Sieve of Eratosthenes
	int phi[n+1];
	for (int i = 0; i <= n; ++i) {
		phi[i] = i;
	}
	for (int i = 2; i <= n; ++i) {
		if (phi[i] == i) {
			for (int j = i; j<=n; j+=i) {
				phi[j] = phi[j] - phi[j]/i;
			}
		}
	}
	printf("\nThe euler totient function for all integers from 1 to %d is:\n",n);
	for (int i = 1; i <= n; ++i) {
		printf("%d: %d\n", i, phi[i]);
	}
	return 0;
}

/*
Time Complexity: O(N loglogN)

OUTPUT
Enter an integer: 10
The euler totient function for 10 is: 4
The euler totient function for all integers from 1 to 10 is:
1: 1
2: 1
3: 2
4: 2
5: 4
6: 2
7: 6
8: 4
9: 6
10: 4


-----
(1,3,7,9) are coprime to 10
*/