Is This a New Idea... ( Prime Sieve )
TranslucentAmoebae
On my Blog...
http://transamoebae.blogspot.com/2005/08/is-this-number-prime.html
D Herring
Not new, although your approach is somewhat different. Unfortunately,
converting numbers between bases is a fairly expensive operation in
itself; there are more efficient methods of identifying primes.
Modern prime-detection routines don't directly search for divisors, they
just test conditions that most composite numbers will fail. Pass 10
different tests that 99% of composite numbers will fail, and you are
probably prime.
Here are some pages you might like to read about prime theory:
http://mathworld.wolfram.com/SieveofEratosthenes.html
http://mathworld.wolfram.com/PrimalityTest.html
http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html
If you want to generate your own exhaustive list of primes (say all
primes less than 100000), the sieve of Eratosthenes gets rather
inefficient. A slightly faster method is to generate an offset table...
If you take the first two primes (2,3), they will mask out numbers in a
periodic pattern of length 6. So, starting with 5 (the largest prime <
2*3=6), possible remaining primes are at +2,+4... The first few
iterations give 5,+2=7,+4=11,+2=13,+4=17... This is an easy trick to
remember, and its useful to generate a prime table by hand up to a hundred.
For a bigger table, take the first three primes (2,3,5); they generate a
mask of period 30. So, starting with 13 (the largest prime<3*5=15),
possible remaining primes are at +4,+2,+4,+2,+4,+6,+2,+6... By storing
these 10 offsets, 30-10=20 composite numbers are avoided. You can
easily make such offset tables for the first N primes. However, after a
short time, the table length grows faster than the rate of eliminating
composites. For fun, you can compare the number of elements in the
table to the table's period and get an upper bound on what percentage of
numbers are prime.
2 primes: 2/6=1/2 -> less than half of the integers are prime
3 primes: 10/30=1/3 -> less than a third
...
Some prime lists:
http://www.rsok.com/~jrm/printprimes.html
http://primes.utm.edu/primes/home.php
http://www.mersenne.org/
Enjoy primes, but beware! They can become an obsession. (As can
palindromes; especially trying to predict how many iterations of the
"reverse and add" routine are required to convert any integer into a
palindrome).
:)
Daniel