best way to find a prime number

Question

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

Answer 1

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 2

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 3

Inspired by xkcd:

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

Answer 4

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 5

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

Answer 6

There are two different questions:

1) How to find if a number is a prime number? If you discover an efficient algorithm for this one, you will be famous for the next 2000 years ;)

2) How to find the prime numbers up to a limit N?

probably this is what you are asking about. Sieve of Atkin is the most efficient one If your range or limit N is really big number. In reasonable ranges, you could implement an optimized variation of Sieve of Eratosthenes. I found these two sites to be more than useful:

• The Black Key Sieve
• The Sieve of Eratosthenes

EDIT: @avakar

While I am more than beginner on the subject, I don't think AKS is the waited algorithm! From the same source:

However, some composite numbers also satisfy the equivalence. The proof of correctness for AKS consists of showing that there exists a suitably small r and suitably small set of integers A such that if the equivalence holds for all such a in A then n must be prime.

Answer 7

Take a look at existing libraries e.g. OpenSSL and GNU MP.