3

I recently came across this question in a hiring challenge :

Given an interval [L, R] (1 <= L,R <= 10^5), we need to tell number of coprimes of K in interval [L, R] for each K in [L, R].

e.g. L = 3, R = 7

for K = 3, number of coprimes in [3, 7] = 3 (4, 5, 7)

for K = 4, number of coprimes in [3, 7] = 3 (3, 5, 7)

for K = 5, number of coprimes in [3, 7] = 4 (3, 4, 6, 7)

...

By my approach, I am finding prime numbers upto R and then for each K, by its prime factors, counting number of coprimes, but I need better and efficient approach than this. Thanks in advance.

Pratik Kale
  • 153
  • 8
  • 2
    hi pratik , it would be much better if you posted snippets of your code. whenever you post a question please put the code too – Shoyeb Memon Nov 15 '19 at 07:21
  • Wow, this is hiring challenge seems unreasonably hard. It needs math knowledge. Do you know about inclusion-exclusion theorem? – Pham Trung Nov 15 '19 at 08:21
  • 1
    Read answer from @qwertyman, it is actually quite close to what I am thinking. One thing to notice is for a number < 10^5, there should only be at most 9 unique prime in its factorization, even smaller (9! > 10^5). Second, we could use sieve of eratosthenes to quickly calculate all prime factors of number from 2 to 10^5 – Pham Trung Nov 15 '19 at 08:27
  • 1
    @PhamTrung its variant *[the smallest factor sieve](https://stackoverflow.com/a/16060180/849891)* to be exact, which stores a number's smallest factor instead of the Boolean. – Will Ness Nov 15 '19 at 09:14

1 Answers1

4

One approach would be the following.

For every number K perform the following steps:

  1. find the prime factors of K (let us denote this set as D).
  2. use inclusion-exclusion principle to count the numbers in the [L, R] interval which are multiples of at least one number in D. This number will represent the count of the numbers which are NOT co-prime with K.
    • you can see more details about this inclusion-exclusion approach in this answer (of mine).
    • that question involved arbitrary sets D (not necessarily comprising of prime numbers) -- in our case D contains prime numbers, thus the lowest common multiple (lcm) call from that answer can be computed more directly here as the product of the numbers in the current subset.
  3. finally, to find the number of co-primes with K, subtract the previously found number from the total number of values in the [L, R] interval.

Remark: in step 2 we can similarly use the inclusion-exclusion principle to directly count the numbers which are co-prime with K (however, it feels more natural to me to count the multiples of numbers in set D). This would not require step 3 anymore.

danbanica
  • 3,018
  • 9
  • 22
  • I have thought about this approach earlier, but, I think number of subsets of prime factors will be out of bound to use inclusion-exclusion – Pratik Kale Nov 15 '19 at 07:34
  • it might still be feasible -- there are at most |D| = 6 prime factors for every number less than 10^5 (because 2 * 3 * 5 * .. * 17 > 10^5), so at most 64 subsets (however, only a few K will have 6 prime factors). Every subset can be processed in O(|D|). We can additionally improve the execution time by considering that there are multiple numbers K that have the same set D. – danbanica Nov 15 '19 at 08:36
  • 1
    Yes, got it now, we can apply inclusion-exclusion here. Thanks. – Pratik Kale Nov 15 '19 at 08:42