How fast can we find primes (number of computations needed+time for the computation too) So, I know we can get a bound on how long it will take to find a large prime. For example, using the fact that between $N$ and $2N$ there must be a prime. And the fact that all numbers between are prime iff they do not have a divisor less than $\sqrt{2N}$. So, this gives us one bound on the amount of time needed. (Assume that we know all the primes less than $\sqrt{2N}$.) Then the number of computations is at most $N\sqrt{2N}$ to find one prime.
Can this result be improved? In general, how long (# of computations * time per computation) does it take to find a new prime of size $N$
edit: ***The number of computations is at most $N \ln \sqrt{2N} $ Using the PNT.
 A: The usual way to generate big primes is simply choose at random large numbers and test whether they are prime or not. The prime number theorem shows that you have a chance of about $\frac{1}{\ln n}$ to stumble on a prime that way, $n$ being your upper bound. In practice this can be (roughly) translated to "the number of failed attempts is the same order of magnitude as the number of digits in the prime you are attempting to generate", so a 2048-bit prime will take about 2,000 attempts even without any smart optimization - not that bad.
The main question is how to test that a number is prime. In practice, first attempt to divide by the first 100 primes or so. If that fails, run the Miller-Rabin test as it is very fast ($O(\ln ^3n)$). Miller-Rabin is probabilistic, so it might fail (tell you that a composite number is prime; never the other way around), but with the reasonable security parameters you can guarantee that the chance for an error is virtually nothing (even if you run Miller-Rabin for the rest of your lifetime, no error is expected).
If you must be 100% sure you have a prime, the AKS test will work, although it is much slower than Miller-Rabin. There are other methods of primality proving, such as the elliptic-curve test; they won't always work efficiently, but they're worth a try.
For further reading, try "Prime Numbers" by Crandall and Pomerance, which deals exactly with these topics.
