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.

66% Solution Ratio

MeekgeekEarliest,

Deshi_TouristFastest, 0.0s

PIS_ShamiLightest, 1.3 MB

deepGooglerShortest, 511B

Toph uses cookies. By continuing you agree to our Cookie Policy.