Consider receiving as input $x\in\mathbb N$ and computing some (any) prime $p\in[x,2x]$.
What is the complexity of the above problem?
A natural way to approach this problem is to generate random integers in $x,\ldots,2x$ and check for their primality using Miller-Rabin or a deterministic algorithm such as AKS.
However, this may be suboptimal. What is the best-known runtime for the problem?