# Time complexity of finding an integer between $x$ and $2x$

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?

• Dec 25 '17 at 16:27

You can speed up this algorithm somewhat by generating a random integer which is coprime to all small primes. This can be done efficiently using a sieve: pick an appropriately sized random interval inside $[x,2x]$, and cross off all integers in the interval which are multiples of small primes (you can do this efficiently by finding the first multiple of a given prime, and then iterating over the remaining multiplies). Now use your favorite algorithm to find a prime within the integers not ruled out. The size of the interval should be chosen so that it guarantees that there is a prime (so about $\log x$ or somewhat larger).