Time complexity of finding an integer between $x$ and $2x$
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).