What is the best way to find a prime number? [closed]

Question

what will be the best way to find a prime number so that the time complexity is much reduced.

Answer 1

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.

Answer 2

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.

Answer 3

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/

Answer 4

Inspired by xkcd:

int findPrimeNumber() {
    return 2; // guaranteed to be prime
}

Answer 5

If you want to generate primes from 1 to whatever, then the fastest way is probably a wheeled Sieve as implemented here, which can typically test more than 3,000,000 candidate primes a second on an average laptop (and that's using an unoptimized language like VB.net), and factor the non-primes to boot. In c++ it could be easily 5 to 20 times faster.

Answer 6

Although there are more efficient algorithms, the Miller-Rabin primality test is one of the simplest tests to implement.