### Primarily random

Jul. 10th, 2009 12:25 amIs it unrealistic to think of the primes as a sort of hologram for the integers, since you can generate any integer by multiplying the necessary primes together?

Isn't it interesting, given the ease with which they can be used to create all of the other integers, that there is apparently no direct way to generate the prime numbers from themselves? (Is there a name for that?)

These thoughts brought to you by the fact that I just implemented an algorithm to find all the primes using a method inspired by the Sieve of Eratosthenes. (Start with 2 as a known prime, testing 3. Attempt to divide the test number by all of the known primes. If any of them divide it cleanly--no remainder--discard it. If none of them divide it cleanly, it is prime; add it to the collection.) This is sufficient because all of the non-prime integers are products of some collection of prime integer and therefore a number is divisible by a non-prime integer if and only if it is also divisible by a prime integer. So you can save a lot of time by not doing the checking of non-prime integers.

That having been said, I'm only up to the high 60000's. The fact that I'm doing this with a HugeInt class that I wrote myself to remove the limitation of the computer's native 4-byte integer appears to be moot, as I suspect that even if I left this to run forever I might very well die of old age before that became relevant.

~ponder~ I wonder what would happen first: me die or the computer use up all its RAM. (Annnnd we're back to signal processing and frequency analysis ~grin~)