to count the intervals A finite set of two or more consecutive natural numbers is called a "co-prime interval" if there is no number in it that is co-prime to all other numbers in the set.
Given a range [A, B], I would like to count the number of  co-prime intervals completely contained in it. i.e., I want to know how many different pairs (a, b) exist such that A ≤ a < b ≤ B and the set {a, a+1, ..., b} is a co-prime interval.
test cases:
Input:
4
$2184$ $2200$
$2185$ $2200$
$2184$ $2199$
$1$ $100000$
Output:
1
0
0
13
explanation:
[2184,2200] is a co-prime interval because it does not contain any other co-prime interval. 
[2185,2200] is not a co-prime interval because 2197 is co-prime to all other numbers in that range.Same thing goes for [2184,2199] with 2189, so the answer to queries 2 and 3 is 0 (because again they don't contain any other co-prime interval). 
The answer to the 4th query is 13 because there are 13 different co-prime intervals contained in the range [1,10^5].
I am looking for the optimal solution apart from the usual approach by trying every possible number in the range [A,B].
can someone help me with this.
thanks
 A: This is an overlong comment (or might turn into a solution over time). At least it may give some hints to possible approaches.
Lemma 1. The length of a coprime interval is $\ge 5$.
Proof. If the length is $1$, the the only element is trivially co-prime to all others. If the length is $2$, the two elements are consecutive, hence coprime. If the length is $3$, the middle element is coprime to both its neighbours.
If the length is $4$, there are exactly two odd elements, but at distance $2$ they cannot have an odd common divisor. One of them is not at the end of the interval, hence also coprime to the even members, its neighbours. $_\square$
Lemma 2. If $[a,b]$ is coprime, then all its members are composite.
Proof. Assume otherwise and let $p$ be the greatest prime in $[a,b]$ (apart from composites and priems, we also have $1$, but $1$ is coprime to everything). Then anotther multiple of $p$ must be in the interval, i.e. $b\ge 2p$. But by Bertrand's postulate, there exists a prime $q$ with $p<q\le 2p$, contradicting the maximality of $p$. $_\square$
Let $S_0$ be the set of primes, $\cup\{1\}$.
Given $S_n$, let $S_{n+1}$ be $S_0$, enlarged by all numbers $m$ with the following property: Let $s=\max(S_n\cap\{1,\ldots,m-1\})$ and $t=\min(S_n\setminus\{1,\ldots,m\})$; then $m$ is added if $t-s\le 5$ or the smallest prime factor of $m$ is $\ge \max\{m-s,t-m\}$.
Finally, let $S=\bigcup_n S_n$.
Lemma 3. If $[a,b]$ is coprime, then $[a,b]\cap S=\emptyset$.
Proof. It follows by induction that $[a,b]\cap S_n=\emptyset$ for all $n$: The case $n=0$ is lemma 2. If $[a,b]\cap S_n=\emptyset$, then for $m\in[a,b]$ with $s<m<t$, $s,t\in S_n$, we have $s<a\le m\le b<t$ and hence: if $t-s\le 5$ we arrive at a contradiction from lemma 1; and if all prime factors of $m$ are $\ge m-s$ and $\ge t-m$, then $m$ is coprime to all numbers in $[s+1,t-1]$, again a contradiciotn. we conclude ta also $S_{n+1}\cap[a,b]=\emptyset$. $_\square$
It is possible to enumerate the elements of $S$ by a computer program quite fast (for not too ambitious ranges) in ascending order. In turns out that the complement of $S$ is
$$\tag1\mathbb N-S=[2184, 2200] \cup
[27828, 27846] \cup
[32214, 32230] \cup
[57860, 57876] \cup
[62244, 62260] \cup
[87890, 87910] \cup
[92274, 92290] \cup
[110990, 111010] \cup
[117920, 117936] \cup
[122304, 122320] \cup\ldots
 $$
Within these relatively rare candidate intervals, it seems already promising to do a more or less brute-forvce search. (This search can still be quite fast if one does bookkeeping about the minimal prime factor of each number in the interval)
Here's a suggested algorithm to count the coprime intervals contained in $[A,B]$ where $[A,B]\cap S=\emptyset$ (i.e. is one of the intervals occurring in $(1)$ or a subinterval of such an interval):


*

*Set $N\leftarrow 0$.

*Set $a\leftarrow A$.

*Set $b\leftarrow a$ and $m\leftarrow a$.

*Let $p$ be the smallest prime divisor of $m$.

*If $m-p<a$ and $m+p>b$ set $b\leftarrow m+p$. If this makes $b>B$, go to step 8.

*If $m=b$ increase $N$ and $b$ by $1$. 

*Increase $m$ by $1$ and go to step 4.

*Increase $a$ by one.

*If $a>B-4$ terminate with $N$ as the asnwer. Othrewise go to step 3.


It may be worthwhile to cache the divisors computed in step 4.
Also, I suspect that it is not less efficient to use only a simple approximation to $S$ auch as $[1,2183]\cup [2201,27827]\cup\{\text{primes}\}$
