What is the best way to find a prime number?

When it comes to finding prime numbers, the Sieve of Eratosthenes and the Sieve of Atkin are two possible solutions. The Sieve of Eratosthenes has a complexity of O((n log n)(log log n)). The Sieve of Atkin has a complexity of O(N / log log n).

If you have a number and you want to find out if it's prime, that is called performing a primality test. The naive approach is to check all numbers m from 2 to sqrt(n) and verify that n % m is not 0. If you want to expand this slightly, you can throw out all even numbers (except 2). There are also some other enhancements to this naive approach that might improve performance, along with other, more advanced techniques.

Use sieve of Eratosthenes is if you want to enumerate primes. If you want to generate a large prime, generate a random odd number and check for primality.

If it's below a certain range, best way would be to look it up in a precomputed list. There's plenty of them, up to very high numbers.

Example, all the primes up to 10,000,000,000 at http://www.prime-numbers.org/