Euler Totient Function | Editorial by Susanka

Euler's totient function, also known as phi-function ϕ(n), counts the number of integers between 1 and n inclusive, which are coprime to n. Two numbers are coprime if their greatest common divisor equals 1 (1 is considered to be coprime to any number)[read more](https://cp-algorithms.com/algebra/phi-function.html)
```
#include<bits/stdc++.h>
using namespace std;
int phi(int n) {
    int result = n;
    for (int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            while(n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if(n > 1)
        result -= result / n;
    return result;
}

int main() {
	int t;cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		cout<<phi(n)<<'\n';
	}
	ber).`#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int phi(int n) {
    int result = n;
    for (int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            while(n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if(n > 1)
        result -= result / n;
    return result;
}

int main() {
	int t;cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		cout<<phi(n)<<'\n';
	}
	`
```

Euler Totient Function | Editorial by Susanka

Download submission

All caught up!

View submission

Is your resume even shortlisted?