Euler’s Totient Function (SPOJ ETF)

Problem Link: problems/ETF/

Reading Materials:

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 !


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;
return 0;
view raw spoj_ETF.cpp hosted with ❤ by GitHub

“For every complex problem there is an answer that is clear, simple, and wrong

H. L. Mencken

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website with
Get started
%d bloggers like this:
search previous next tag category expand menu location phone mail time cart zoom edit close