CODEWITHSUNDEEP
algorithmmathdata-structuresprimes
Pratik Kale
Pratik Kale

Reputation: 163

Count of Coprimes for each number

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.

Upvotes: 4

Views: 654

Answers (1)

danbanica
danbanica

Reputation: 3038

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.

Upvotes: 4

Related Questions