# Editorial for Hidden Graph

We can easily precalculate the prime divisors of each number using $Sieve of Eratosthenes$.

For each test case, We will connect each numbers node, with its prime divisors node.
We can simply use $BreadthFirst Search$ to find the number of connected components and their size. While counting, we have to exclude the nodes that are not in range from $L$ to $R$.

Time Complexity: $O( N × log(N) )$ for precalculation where N = $10^6$. And $O(T × R × Log(R))$ for test cases.

### Statistics

66% Solution Ratio

MeekgeekEarliest, 3M ago

Deshi_TouristFastest, 0.0s

PIS_ShamiLightest, 1.3 MB