Best algorithm to tell if an odd semi prime exists between a given pair of even semi primes.

Question

Problem:

Let two even semi primes be $2q_1$ and $2q_2$: you are to find if any $n$ exists such that $n$ is odd , $n$ is semi-prime and $2q_1 < n < 2q_2$. We don't need to know the $n$ , we just need yes or no answer.

My approach:

The approach I can think of is:

$$ \pi(2q_2/3)-\pi(2q_1/3)\\ \pi(2q_2/5)-\pi(2q_1/5)\\ \pi(2q_2/7)-\pi(2q_1/7)\\ \vdots \\ \pi(2q_2/p_k)-\pi(2q_1/q_k)$$

i.e. primes under $2(q_2-q_1)$ times.

If any of these lines is non-zero answer is yes.

$\pi$ is Exact Prime-counting_function

The computational complexity of this would be = O(number of primes under [2(p_2-p_1)] * complexity of best known exact prime counting function). = $O(n/log(n).(n^{2/3}/log^2(n)))$ = $O(n^{5/3}/log^3(n))$

My approach is definitely extremely inefficient, looking for better ones.

Edit:

The approach which @Peter suggests to traverse through all numbers in the range has time complexity $O(n.n^{1/4})$ = $O(n^{5/4})$ which isn't much efficient either.

Both the above approach uses no additional memory[ie $O(1)$ memory complexity] . For sake of simplicity we can assume we have infinite memory for any pre-computation/offline processing that you can think of.

Answer 1

The major optimization is to use approximate formulas for maximal prime gaps to return yes when p1 and p2 are far apart. Specifically https://en.wikipedia.org/wiki/Prime_gap#Numerical_results provides maximal prime gaps for numbers up to 2^64 (e.g. the maximal gap for numbers below 10^9 is 114, so if 2/3(p2-p1)>144 and p2<10^9 you can just return true. For larger values explicit gaps aren't known, but there are useful upper bounds on gap sizes. Specifically, the prime gap at n is always less than 3(n^2/3+n^1/3+1) for x>e^e^15 by https://arxiv.org/abs/0810.2113.

There are also a number of much stronger conjectures on prime gaps. With the Riemann hypothesis, the maximal gap can be lowered to O(sqrt(n)log(n)), and there are even stronger conjectures of O(log(n)^2) (although these are much more controversial).

After this, I think your best bet is to just do your approach with a few differences. The main one is that you can compute pi(x)-pi(x+delta) efficiently by doing delta primality checks. You also don't have to search as many ranges as your original estimate since most of the intervals won't contain any numbers.

Also, it's worth noting that given the various conjectures on prime gaps, it's very likely that if there isn't a prime in (2/3p1, 2/3p2) then they are very close together.