Problem Link: problems/ETF/

Reading Materials:

- https://forthright48.com/euler-totient-or-phi-function/
- https://cp-algorithms.com/algebra/phi-function.html
- https://www.geeksforgeeks.org/eulers-totient-function/

I believe anyone can have enough knowledge about Euler Phi from these sites. That’s why no explanation on this topic. The problem is a cakewalk of euler phi. Have a great day, Code on !

## Code:

#include<bits/stdc++.h> | |

using namespace std; | |

#define ll long long | |

int phi(int n) { | |

int ans = n; | |

for (int i = 2; i * i <= n; i++) { | |

if(n % i == 0) { | |

while(n % i == 0) | |

n /= i; | |

ans -= ans / i; | |

} | |

} | |

if(n > 1) | |

ans -= ans / n; | |

return ans; | |

} | |

int main() | |

{ | |

ll tc,idd=0,b,n,temp,r,i,p,q,c,ans; | |

scanf("%lld",&tc); | |

while(tc--) | |

{ | |

scanf("%lld",&n); | |

printf("%d\n",phi(n)); | |

} | |

return 0; | |

} |

“For

— H. L. Menckeneverycomplexproblemthere is an answer that is clear, simple, andwrong“