We have given two numbers $x$ and $p$. We want to count how many numbers are less than $x$ and are co-prime with $p$.
I know that we can solve the problem in $O(x\log x)$ with iterating over all numbers less than $x$ and check if their greatest common divisor is $1$.
Is there any way to solve this faster, because I think that we can reduce this somehow. Please give some hints on where to start working.
There's a very fast method if p has few prime factors. Say p is a prime. Then the numbers co-prime with p are all numbers other than p, 2p, 3p, 4p etc. There are x-1 numbers less than x, and of those floor ((x-1) / p) are divisible by p, so exactly (x-1) - floor ((x-1) / p) are co-prime with p. For simplicity, let f(n) = floor ((x - 1) / n), then for a prime p the result is f (1) - f (p).
If p has two prime factors a, b, then we would start with f(1) - f(a) - f(b) - take all numbers, except those divisible by a, except those divisible by b. But here is a mistake: Numbers divisible by ab have been removed twice, so we add them back: f(1) - f(a) - f(b) + f(ab).
For three prime factors a, b, and c, we use the same scheme and start with f(1) - f(a) - f(b) - f(c) + f(ab) + f(ac) + f(bc). Numbers divisible by abc have been removed three times, added back three times, and therefore need to be subtracted once, giving f(1) - f(a) - f(b) - f(c) + f(ab) + f(ac) + f(bc) - f(abc).
You can continue this. You'll have to figure out yourself what exactly to add or subtract. With k different prime factors, you have 2^k terms - but clearly with 10 different prime factors, and say x = 1,000,000, you have only 1024 different terms. Also, as soon as a product is greater than x, you can ignore it. For example, all prime factors ≥ x of p can be completely ignored. And all duplicate prime factors can be ignored.
Actually, the number of different prime factors grows very slowly, so this method is quite good unless x is small.
How many numbers less than a billion are co-prime with $10^{100}$? Prime factors of $10^{100}$ are 2 and 5, so the answer is 999,999,999 - 499,999,999 - 199,999,999 + 99,999,999 = 400 million.
Are you familiar with the Sieve of Eratosthenes? Play around with how it might be used in this case. Your answer likely lies there.
