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 !

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;
}
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:

WordPress.com Logo

You are commenting using your WordPress.com 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 WordPress.com
Get started
%d bloggers like this:
search previous next tag category expand menu location phone mail time cart zoom edit close