Originally Posted by

**Media_Man** Since a = a+kn (mod d) for all d|n, gcd(a,n)=gcd(a+kn,n).

Example: Look at the coprimes of 15: 1,2,4,7,8,11,13,14. Now add any multiple of 15 to them, and you have another, bigger set of coprimes.

So, define f(x,n)= “the number of coprimes of n less than or equal to x”

If x>n, then there are phi(n) coprimes between 1 and n, another phi(n) coprimes between n+1 and 2n, and so on. Therefore, f(x,n)=floor(x/n)*phi(n)+f(x%n, n), where "%" denotes the remainder of x/n.

In other words, adjust your loop to find all the coprimes of n only up to x%n, and add that number to floor(x/n)*phi(n), which you said you already had an “easy” method of computing.

You're much better using an array of numbers 1 to x (x<=n) and striking out prime factors than calling the gcd() function x times, from a computing standpoint, assuming you have a relatively fast way to factor n.