Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!think.com!hsdndev!dartvax!eleazar.dartmouth.edu!ari
From: ari@eleazar.dartmouth.edu (Ari Halberstadt)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Prime numbers == Use Knuth, not tables
Message-ID: <1991Apr18.011001.10511@dartvax.dartmouth.edu>
Date: 18 Apr 91 01:10:01 GMT
References: <1991Apr11.020157.11756@agate.berkeley.edu> <1991Apr11.145247.16673@ux1.cso.uiuc.edu> <1991Apr16.180730.12939@dhw68k.cts.com>
Sender: news@dartvax.dartmouth.edu (The News Manager)
Organization: Dartmouth College, Hanover, NH
Lines: 21

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.