Find the coprime number (gcd(1,n)=1) 1 to n.

Example:  n=1   ,2 ,  10
                phi(n)= 1 , 1,   

gcd(1,10) =1  (include)   1
gcd(2,10) != 1 (not include)
gcd(3,10) =  1 (include) 1+1
gcd(4,10)!=1(not include)
gcd(5,10)!=1(not include)
gcd(6,10)!=1(not include)
gcd(7,10) =1(include) 1+1 +1
gcd(8,10)!=1(not include)
gcd(9,10) = 1 (include)1+1+1+1
gcd(10,10)!=1(not include)

Total 4 numbers between 1 and 10 whose gcd(i,10) =1 

So, Phi(10) = 4


Solution:

# Naive Approach
def gcd(a,b):
if(a==0):
return b
return gcd(b%a,a)

def phi(n):
count=0
for i in range(1,n+1):
if(gcd(i,n)==1):
count+=1
return count




# Effective approach
def phi1(n1):
result=n1
i=2
while(i*i<=n1):
# check if prime factor or not
if(n1%i==0):
while(n1%i==0):
n1=int(n1/i)
result-=int(result/i)
i+=1
if(n1>1):

result-=int(result/n1)
return result

print(phi(200))
print(phi1(20))

Time Complexity==O(sqrt(n))



# Euler phi function in O(Log(n)) Time complexity (Divisior property)

def phi(n):
phi=[]
phi.append(0)
phi.append(1)
for i in range(2,n+1):
phi.append(i-1)
for i in range(2,n+1):
j=i*i
while(j<=n):
phi[j]-=phi[i]
j+=i
return phi

print(phi(10))