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.
1 Like
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