What's the fastest and most efficent way to find prime numbers?

Question

I'm writing a computer program that finds prime numbers. It currently loops through a number (n) and starts at 2 (k). It checks if n is divisible by k. If so, it declares the number as not prime and moves on. If not, 1 is added to k and the division is repeated. This goes on until k is equal to half of n.

Is there a more efficent way to do it?

Answer 1

yes the sieve of Eratosthenes, the sieve of atkin, and the sieve of sundaram would all fit the bill. as would Euler's sieve etc.

Answer 2

Your question needs to be much more specific.

For example, a pathological reading of your question would yield 'while(1)printf("2\n");' as a possible solution.

For bulk prime generation in the 64-bit range, the segmented Sieve of Eratosthenes is the fastest method. Implementation matters, but the current fastest codes (primesieve and yafu) use this, and it's faster than Sieve of Atkin (e.g. primegen) when similar optimizations are applied.

If you're looking for primality tests,

• tiny, e.g. under 1M, trial division with careful attention to small details since every cycle matters.
• 32-bit: small fixed trial division followed by 2-base hashed Miller-Rabin. BPSW is almost as fast.
• 64-bit: small fixed trial division followed by BPSW. There are 3-base hashed Miller-Rabin tests that work to 48-bit but use a large table. There are also deterministic Miller-Rabin sets so you'd need at most 7 Miller-Rabin tests, but this is slower than BPSW. Note that these are not probable prime tests.
• 81-bit: 12- and 13-base deterministic Miller-Rabin tests.

There are a variety of implementation optimizations to speed these up. The main issue is having the fastest mulmod possible, which means a couple assembler instructions since C doesn't have a way to specify this. Even faster is using Montgomery reduction. The basic algorithms are the same in either case.

Once larger than this, there are still lots of questions to answer. For instance, efficient generation of very large primes typically use special forms that have fast proof methods available. This is another topic. Assuming you were looking for general-form numbers, we can continue.

BPSW is probably your best bet. It's quite fast and has no known counterexamples though they may exist. Add a Frobenius test or however many random-base Miller-Rabin tests you'd like if you're paranoid. Use ECPP or APR-CL for a proof if you would like -- they're the most efficient general-form algorithms currently available.

If you're looking for >5k digit primes, then

• gwnum, as used in PFGW for example, is much faster than GMP for this size number. It's a total PITA to program with compared to GMP, but for this purpose we can use PFGW to do a fast Fermat test. That quickly weeds out composites. After than we can use regular GMP code for a BPSW test.
• Pari/GP has a decent APR-CL and there is a GMP open source version. It's probably good to about 10k digits. But ECPP is typically preferred for a number of reasons once we get this large.
• There are a few open source versions of ECPP available, but Primo (free to use, not open source) is the gold standard. It can easily handle 10k digits on multi-core machines, and has been used for inputs of 30k+ digits.
• After 20k or so digits nothing is going to be fast for general form numbers. Even Primo starts taking days.

To generate many large primes, we generally want to pick a range of some width, sieve it to some depth, then perform efficient primality tests on the remaining candidates. This can be done entirely in GMP, or if the numbers are quite large we can use some GMP code to do the partial sieve then run the candidates through PFGW to get probable primes (at this size pseudoprimes are rare), then run those through something like a BPSW test.

To generate large random primes for crypto use, there are a variety of methods each with different statistical and performance tradeoffs. The correct statistics come from the "trivial" method, but people sometimes compromise that for performance.