Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!zardoz.cpd.com!dhw68k!mrx
From: mrx@dhw68k.cts.com (Mark Murphy)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Prime numbers, Help
Message-ID: <1991Apr16.180730.12939@dhw68k.cts.com>
Date: 16 Apr 91 18:07:30 GMT
References: <8742@ucdavis.ucdavis.edu> <1991Apr11.020157.11756@agate.berkeley.edu> <1991Apr11.145247.16673@ux1.cso.uiuc.edu>
Organization: Wolfskill & Dowling residence; Anaheim, CA (USA)
Lines: 29

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
>>primes to 65536 is well under 10K, and can handily be included in a
>>resource.  A binary search will quickly find you the next prime if
>>your input is two-byte integer.
>
>  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. 
>At 1 bit per number, only 8192 bytes are 
>required. Store only the odd numbers (remember to make 2 a special case)
>and the storage drops to 4096 bytes.
>--

   Then scan the table 4 bytes a time starting from the desired position.
This should speed things up.


-- 
+-----------------------------------+----------------------------------------+
| Real Life: Mark F. Murphy         | What kinda beer do you like?           |
|   The Net: mrx@dhw68k.cts.com     | Heineken!?  Intercourse that doo-doo!! |
| The Desktop BBS: 714-491-1003     | Pabst Blue Ribbon!!!                   |