Hi
Dang Rob, that was advanced optimizing 
My advance advice would have been to make a list of known small primes (like all primes from 2-300) and then check a candidate against that list before switching to Eratosthenes sieve.
I once wrote a pyton code that omitted the power hungry modolo operation. You make a list of boolean items in the full range you wanna test and then declare all items "1" (all numbers are primes). Go though the list, if you meet a "1" all multiplication of that number is switched from "1" to "0". After once through the list it will only contain "1" at prime numbers.
As long long as the list chould stay in PC memory without useing swarp files it was super fast.
Oh well, the prime genie is out of the bottle.
-Fletcher
Btw, looks like OP posted the code here:http://arduino.cc/forum/index.php/topic,63073.0.html