I found this question somewhere online, which went as follows:↵
For each integer x in a given range [L, R], find the count of integers in the given range that are co-prime with x.↵
Constraints: 1 <= L <= R <= 1e5↵
↵
A brute force solution would fail the time limit, dExample: For L = 2, R = 4, the co-prime pairs would be:↵
↵
2 -> (2,3) so count = 1↵
3 -> (3,2), (3,4) so count = 2↵
4 -> (4,3) so count = 1↵
↵
Does anyone have an optimal solution for this?
For each integer x in a given range [L, R], find the count of integers in the given range that are co-prime with x.↵
Constraints: 1 <= L <= R <= 1e5↵
↵
↵
2 -> (2,3) so count = 1↵
3 -> (3,2), (3,4) so count = 2↵
4 -> (4,3) so count = 1↵
↵
Does anyone have an optimal solution for this?
