For a given $N$ and a given prime $p_j$ count the number of numbers can you generate in ($N^{0.5}$, $N/p_j$] that are not divisible by any primes $ \ge p_j$
Example: $N=100, p_j=5$
you can generate two numbers i.e. $12$ and $18$
ie $12=2^2.3$
ie $18=2.3^2$
Both the above numbers lie in (10,20]
Hence the answer is $2$.
My idea so far:
if $p_j>N^{0.5}$ answer is always $0$.
Step 1. Shortlist all numbers $a \le N^{0.5}$ such that $a$ is only divisble by primes less than $p_j$.
Step 2. Increment powers of each prime factor gradually to reach the desired range for eample in above exmaples if $a=2.3$. I can increment powers of $2$ and test for how many powers of $2$ keep it is in $(10,20]$. This can be done in $O(1)$. Similarly I can do for $3$ as well.
The tricky cases arise when the power of multiple prime factors can be incremented simultaneously to generate a valid candidate. So this approach is going to be tricker for large ranges as it can have many prime factors.