Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!ncar!gatech!purdue!haven!ni.umd.edu!ni.umd.edu!zben
From: zben@ni.umd.edu (Ben Cranston)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Prime numbers, Help
Summary: Combine prime table with generation routine
Message-ID: <1991Apr17.164107.28457@ni.umd.edu>
Date: 17 Apr 91 16:41:07 GMT
References: <1991Apr4.164338.329@asacsg.mh.nl>
Sender: usenet@ni.umd.edu (USENET News System)
Organization: University of Maryland at College Park
Lines: 24

In article <1991Apr4.164338.329@asacsg.mh.nl> kr@asacsg.mh.nl
(Koos Remigius) writes:

> 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 ...

As stated by others, a fairly small table can hold a bitmap representation
of prime numbers.  For example, a table of 1K bytes can represent all prime
numbers up to 16383.

I seem to remember a theorum that if p1, p2, etc are sequential prime numbers
starting at 2 then numbers of the form

   p1 * p2 * p3 ...  - 1

are prime, the proof concerns the fact that if p1 or p2 or any of the pn are
a factor of the big number then there is a second unique factorization, and
since prime factorizations are unique it must be prime.  Or something.  Or
maybe it was + rather than - -- any mathematicians out there?

Anyway, if you use the table to get the p1, p2, etc you could generate some
incredibly big primes.  The main failure is that they will not be particularly
dense, in fact, the ones at the end of the list will be about 16,000 times
each other.  I don't know *how close* the original requirement was.