ari@eleazar.dartmouth.edu (Ari Halberstadt) (04/18/91)
In article <1991Apr16.180730.12939@dhw68k.cts.com> mrx@dhw68k.cts.com (Mark Murphy) writes: >In article <1991Apr11.145247.16673@ux1.cso.uiuc.edu> rolf@sparc1 (Rolf Wilson) writes: >>lippin@spam.berkeley.edu (The Apathist) writes: >>>Recently kr@asacsg.mh.nl (Koos Remigius) wrote: >> >>>>Is there someone out there who has a little routine, in LightSpeed >>>>Pascal, that gives me the first prime number larger then the number >>>>given to the routine. >>>clever ways to solve the problem, but none of them can touch the brute >>>force approach: include a table of primes in your program. A table of >> If you only need to determine the primality up to 65,536, just include >>a "bitmap" of 0 and 1 to show if each number is prime. Assuming we really want to determine the primality of an arbitrary integer, the best methods use a probability test to weed out nearly all non-primes, then do a brute force check up to the square root of the number being tested. A simple method to do this may be found in one of Knuth's famous trilogy. For finite primes I am not sure which method is faster: a bit array or the Knuth test. A proper comparison would have to pay close attention to the various optimizations possible with division and long integer comparisons.
rberlin@birdlandEng.Sun.COM (Rich Berlin) (04/20/91)
You might check out the _Programming_Pearls_ books. One of them includes some fairly efficient routines for generating primes and for primality testing. -- Rich