2
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ You can stop at $\sqrt n$ for instance, it's better, but it is not the best. $\endgroup$
    – E. Joseph
    Sep 29, 2017 at 18:12
  • 3
    $\begingroup$ Are you trying to find prime numbers, or validate that a given number is prime? They are not the same. $\endgroup$ Sep 29, 2017 at 18:19
  • $\begingroup$ For big numbers, there are efficient tests any of them is deterministic but probabilistic with a high level (practically equal to $1$). For truly very big numbers there is nothing. $\endgroup$
    – Piquito
    Sep 29, 2017 at 18:21
  • $\begingroup$ If you're using a computer, then just use Mathematica's functionality: Prime[n], which gives the nth prime extremely quickly. It can give the billionth prime in $0.000023$ second. $\endgroup$ Sep 29, 2017 at 18:46
  • 1
    $\begingroup$ How sophisticated do you want to get? Trial division is fine and good for small enough numbers, but even moderately large numbers can require some very complex algorithms to give an answer in a reasonable amount of time. $\endgroup$ Sep 30, 2017 at 18:59

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Not when I need to find very high primes. $\endgroup$
    – rappatic
    Sep 29, 2017 at 18:14
  • $\begingroup$ try a segmented version of them ... or even a wheel sieve. $\endgroup$
    – user451844
    Sep 29, 2017 at 18:14
  • $\begingroup$ also all of these would still be faster if you could find the primes to use first. $\endgroup$
    – user451844
    Sep 29, 2017 at 18:15
  • $\begingroup$ From Wikipedia: Wheel factorization is a method for generating lists of mostly prime numbers. $\endgroup$
    – rappatic
    Sep 29, 2017 at 18:16
  • $\begingroup$ still easier than testing unnecessarily composite k's divisibility and testing higher than $\sqrt n$. $\endgroup$
    – user451844
    Sep 29, 2017 at 18:17

Not the answer you're looking for? Browse other questions tagged .