Kenny's point in the comments is a good one as well, and it's also worth keeping in mind that the number of atoms in the observable universe is at most a few orders of magnitude more than 10^80, so writing down all the numbers with 100 or fewer digits is a hopeless task. (Certainly we haven't checked them all for primality!) That said, I'll try to give a rather rough answer to your questions.

1 terabyte, which is a good estimate for the size of a good commercially-available hard drive, is about 2^40 bits. Testing a number that small for primality is very easy (in fact, it's not terribly slow even with naive methods), so you could quite easily and cheaply list all the primes between about 1 and 2^35. Pushing higher than that, things start to get problematic -- there's just not enough space to hold all these numbers! If you gave a 1 TB hard drive to everyone on earth, there wouldn't be enough space to list all the primes between 1 and 2^70, which has about 23 digits. If you pick a random 25-digit number, odds are that it's never been tested for primality before. But it's easy to test such numbers for primality quickly, so this isn't a problem about primes so much as it is about the fact that the exponential function is *big*. So what about prime testing? How fast can we do that?

In practice, the best general method for primality testing seems to be elliptic curve primality proving, probably combined with trial division by small integers. To give you some idea of how efficient it is, the biggest number that's been proved prime by ECPP methods has around 20,000 digits, and the proof took 9 months via a distributed computing project (equivalent to several years on a top-of-the-line general-purpose processor.) A rough back-of-the-envelope calculation suggests that if you want to test for primality in at most a couple of weeks on a single machine, 10000 digits is probably too much, although 1000 seems very reasonable.

Factoring seems much harder. 200 digits is reasonable with a wide distributed computing project, but 2000 is likely to be way out of reach.

knowledge, we might wonder whether every even number, and every multiple of 5, count as numbers that areknownnot to be prime, even if they are numbers that no one has ever happened to write down. If we do count those as known, what about multiples of 7, or 137? There will definitely be some clear cases, but I suspect that at most points in time, there will be some medium-largish number that no one has ever bothered to test for primality, that would take only a moderately long time to test (say, a few hours). Of course, that doesn't address your main question – Kenny Easwaran Oct 21 '09 at 5:42