Euler Totient Function

How can we modify the Euler totient function to get count of numbers less than x(1…x which are co-prime to n) and the numbers are co-prime to n.

2 Likes

This is very common in number theory the formula for finding the number of numbers less than and co-prime with n
is

N(1-1/p1)(1-1/p2)…
where p1,p2… refers to the distinct prime
divisors of the number.

A example always makes it clear ,lets take n=20 hence the prime divisors are 2,5 hence by formula the number of numbers less than and prime to 20 should be 20*(1-1/2)(1-1/2)=20(1/2)(4/5)=8

Now we can count also

1,3,7,9,11,14,17,19

Thus you could use the above formula .

You can find the derivation at any website just google it .
Hope this helps.

1 Like

This is not my question bro. I know the euler totient function. I need to modify it such that it finds the count of numbers from 1 to r which are co-prime to n. r<n where r and n are to be specified by the user.

1 Like