At 02:22 AM 1999/10/16 -0700, Greg Hewgill <[EMAIL PROTECTED]> wrote: >Suppose you were keeping such a list. With one bit (prime vs not-prime) to >represent each number up to 10^15, you would need approximately 10^14 bytes of >storage, which is on the order of 100 terabytes. That would be your first >problem. The second problem would be if you were to present me with the >smallest number that was not factored, I could almost immediately present you >with a factorization (or show that it's prime). The data becomes pretty sparse in bitmap format. With a little work we could do quite a bit better than that. First, the evens greater than two are known composite, so they need not have bits representing them. Second, the primes rapidly get sparse enough that it is more effective to record in several bits, the gaps between primes, or a multilevel lookup, than a simple yes-no table one bit per odd number. Third, if the usual data compression methods are more effective than such a table construct, we could use those compression methods. To answer Gordon Bower's question, very partially, Hans Riesel wrote (in Prime Numbers and Computer Methods for Factorization, 1985, Birkhauser) that in 1909 D N Lehmer published a factor table and prime table covering up to 10,017,000, and in 1959 C L Baker and F J Gruenberger published a table containing the first 6 million primes (all those below 104,395,289). And there have been a few posts if I recall correctly of how little time it takes on a modest speed computer to sieve up to 2^32 (~4,000,000,000+) http://www.utm.edu/research/primes/ contains a link to the Nth prime page at http://www.math.Princeton.EDU/~arbooker/nthprime.html "Enter 1 for the first prime (2), 2 for the second (3), on up to 1000000000000 for the trillionth prime (29,996,224,275,833)." So presumably the region that has been exhaustively searched for general primes is well above 3x10^13. Can someone else out there answer more precisely? On Fri, Oct 15, 1999 at 01:03:57AM -0800, Gordon Bower wrote: > PS - On an unrelated note --- what is the smallest natural number that is > not known whether it is prime or composite? Ken _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
