Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uwm.edu!ux1.cso.uiuc.edu!sparc1!rolf
From: rolf@sparc1 (Rolf Wilson)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Prime numbers, Help
Message-ID: <1991Apr11.145247.16673@ux1.cso.uiuc.edu>
Date: 11 Apr 91 14:52:47 GMT
References: <1991Apr4.164338.329@asacsg.mh.nl> <8742@ucdavis.ucdavis.edu> <1991Apr11.020157.11756@agate.berkeley.edu>
Sender: usenet@ux1.cso.uiuc.edu (News)
Organization: University of Illinois at Urbana
Lines: 23

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.

>This is one of those situations where you can think up a zillion
>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.
--

Rolf Wilson   Illinois State Geological Survey   rolf@sparc1.isgs.uiuc.edu