# What is the time complexity of a Turing Machine that iterates through each prime number from 2 to K (assume oracle generates the next prime)?

Let NextPrimeNumber be an oracle that accepts a prime number n and returns the smallest prime number m such that m > n. It can be called by a Turing machine and returns the answer in constant time.

Let F be the Turing Machine that receives K a positive integer as a number. Suppose its code is the following:

current_prime = 2
while (current_prime <= K):

What is the time complexity of F?
If we printed out all numbers from 2 to K then it would take exponential time in terms of the bit length k of K. However we only iterate only over the primes, not all numbers from 2 to K. I believe primes represent 1/ln(K) of primes less than or equal to K. Therefore the time complexity would be: (2^k)/ln(K) - which would still be exponential or at least super-polynomial?
The running time is $$O(K/\ln K)$$. This is an exponential running time: the input takes $$\lg K$$ bits (assuming $$K$$ is specified in binary), so the running time is exponential in the length of the input. If you set $$k=\lg K$$, then the running time is $$O(2^k/k)$$, which is an exponential function of $$k$$.