This is my first post in this forum.
Here is my problem
The Euler's totient function i.e fi(n) gives us the total numbers that are relatively prime(co-prime) with n in the range [1,n-1]
However i wish to find the number of co-primes of n in the range [1,x]
where x<=n or x>=n.
Wait.... here is the catch.. i need to write a computer program to do so.
Let me elaborate....so that you guys don't think that this is a homework problem or i haven't worked hard enough on this problem.
An easy way to do so is have an array form [1,x] and then strike out all the multiples of prime factors of n.
example : n=30, x=35
prime factors of 30 = 2*3*5
So strike out all the factors of 2 and 3 and 5 from 1 to 35. That would give the answer. Please note that I don't need to find those numbers, i just need the count them i.e how many are co-prime to 30 in the range [1,35].
Another approach could be:
so answer is the value of counter
from i=1 to x
if( gcd(i,n) == 1)
However both of these problem are very slow as in my case
I need a method(or formula) that could quickly find the number of co-primes of n in a range [1,x]
for example if x=n then i can use Euler' totient function... that's easy... but what if x!=n ?
Kindly help me.. i have been searching a solution(that would be fast enough) for the past 3 days and that lead me to this site.
I bet there must be some formula or method that i am missing.
I hope i explained my problem
Thanks for your patience.