Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!agate!spam.berkeley.edu!lippin
From: lippin@spam.berkeley.edu (The Apathist)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Prime numbers, Help
Message-ID: <1991Apr11.020157.11756@agate.berkeley.edu>
Date: 11 Apr 91 02:01:57 GMT
References: <1991Apr4.164338.329@asacsg.mh.nl> <8742@ucdavis.ucdavis.edu>
Sender: usenet@agate.berkeley.edu (USENET Administrator)
Reply-To: lippin@math.berkeley.edu
Organization: Authorized Service, Incorporated
Lines: 27

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're looking in the four-byte range, a full table of primes would
be cumbersome, but the two-byte table gives you one of the world's
fastest primality tests: try dividing your target by each member of
the table in turn.  Using this test, it's a fairly quick task to
search odd numbers for the next prime.

If you really want arbitrary (or even much longer) integers as input,
then it's time to investigate more sophisticated methods.

					--Tom Lippincott
					  lippin@math.berkeley.edu

	"Oh, I could tell you why the ocean's near the shore..."
					--The Scarecrow