In: Computer Science
[PYTHON] Two natural number p,q are called coprime if there are no common prime factors in their prime factorization. E.g. 15 and 20 are not coprime because 5 is a common prime number in their prime factorization, while 20 and 9 are coprime. The Euler’s phi function, φ(n), counts the number of all natural numbers ≤ n which are coprime to n. E.g. φ(9) = 6, as all natural numbers ≤ 9 are 1,2,3,4,5,6,7,8,9. And out of these, the numbers coprime to 9 are 1,2,4,5,7 and 8, a total of 6 natural numbers.
You are required to write a Python function totient(n) that accepts a natural number as input argument and returns the following:
1. a list of all the natural numbers less than or equal to n which are coprime to n; and
2. the result of the Euler’s phi function when run on n.
E.g. totient(9) should return [1,2,4,5,7,8], 6
You can use your function prime factors from Problem 2. to determine if two numbers are coprime or not.
#source code:
def prime_factor_gcd(value,num):
if(value==0):
return num
else:
return
prime_factor_gcd(num%value,value)
def Totient(n):
totient_list=[]
sum=0
for i in range(1, n):
if(prime_factor_gcd(i,n)==1):
totient_list.append(i)
sum+=1
return totient_list,sum
num=int(input("Enter natural number:"))
list,count=Totient(num)
print("totient({}):{},{}".format(num,list,count))
#output:
#if you have any doubt comment below...