3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This method is commonly known as the "Inclusion-Exclusion principle". $\endgroup$ – Jakube Sep 19 '18 at 8:22
3
$\begingroup$

Are you familiar with the Sieve of Eratosthenes? Play around with how it might be used in this case. Your answer likely lies there.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.