Slashdot

There are infinitely many prime numbers. [wikipedia.org]

The oldest known proof for the statement that there are infinitely many prime numbers is given by the Greek mathematician Euclid in his Elements (Book IX, Proposition 20). Euclid states the result as "there are more than any given [finite] number of primes", and his proof is essentially the following:

Consider any finite set of primes. Multiply all of them together and add 1 (see Euclid number). The resulting number is not divisible by any of the primes in the finite set we considered, because dividing by any of these would give a remainder of 1. Because all non-prime numbers can be decomposed into a product of underlying primes, then either this resultant number is prime itself, or there is a prime number or prime numbers which the resultant number could be decomposed into but are not in the original finite set of primes. Either way, there is at least one more prime that was not in the finite set we started with. This argument applies no matter what finite set we began with. So there are more primes than any given finite number.

Keep in mind these are typically 1024-bit (or more) numbers -- 2 ^ 1024 possible numbers to factor. Also, the world's record for factorization at the moment is for factoring a 668-bit number that took "several months of computer time using the combined power of 80 AMD Opteron CPUs. [wikipedia.org]"

Just a matter of looping through all known primes, seeing if x divides by it. That's order 1 since the number of primes is "fixed". If you don't find anything it divides by, it's a new prime (add it to your list) or its smallest factor is larger than your biggest known prime. Otherwise remember that factor, and start working on the dividend.

Check yourself there. It takes longer to perform division on larger numbers (say O(ln(N)^2), though a lot of this depends on the algorithm). If you plan to do the sieve of eratosthenes as you describe (the hard way), that's going to be another O(n*ln(ln(N)) for a total of O(n*ln(N)^2*ln(ln(n))) for each factor.

The sort of numbers you are thinking about when you say that testing via division is O(1) with hardware are 64 bit integers. The sort of semi-primes used in cryptography are on the order of 512 bits, and so (by the formula above) would take roughly 147, 184, 841, 669, 860, 395, 336, 238, 071, 097, 320, 918, 206, 612, 375, 539, 181, 907, 207, 001, 765, 334, 079, 455, 842, 963, 079, 473, 553, 687, 769, 537, 122, 026, 054, 410, 625, 268, 901, 031, 540, 756, 829, 794, 467, 840, 000 times as long.

So if your computer took a nanosecond to solve a 64 bit case (making it faster than the fastest consumer system presently available), and you had a million of them, and all 6 billion people on Earth were your friends, and each of them had a million of these uber boxes as well, and you had a way to collaborate on the problem with no overhead, it would still take you roughly 1, 920, 658, 729, 429, 876, 148, 289, 055, 386, 140, 718, 898, 913, 520, 422, 922, 263, 604, 244, 594, 006, 798, 154, 722, 944, 671, 495, 344, 450, 391, 916, 549, 249, 431, 238 times the age of the universe to factor one such number.

That's why nobody does it that way, and why it's considered a hard problem even though it might sound easy.

-- MarkusQ