Suppose that there is a prime number. Now I want to approximate the next prime number. (It does not have to be exact.) What would be the time-efficient way to do this?
Edit: what happens if we limit the case to the prime number of the form $4k+1$ where k is a natural number?
Edit: it's fine to replace approximate prime number with finding any prime number that is bigger than the given prime number in a time-efficient way.