I'd been meaning to do this for a while, and when I got a bag of colorful little breadboards, it was TIME.
This is a rebuild of the TeensyPrime project I built a while ago, using a separate breadboard that's almost too small (I had to use magnet wire to fit some of the connections) and a microcontroller that's almost too small. The ATTiny13A is a neat chip: AVR with 1K of flash, 64 bytes of RAM and 64 bytes of EEPROM. I programmed it using a Teensy-2.0-based waldo running Ward Cunningham's TXTZYME.
The programming for this is actually kind of interesting. Every time you push the button, the AVR retrieves the currently-displayed number (which is stored in EEPROM), and then increments it, clicks the counter, and tests for primality. If the number isn't prime, it increments and clicks again. When a prime number is reached, it stops and waits for another button press. But how do you (relatively) efficiently test for primality of numbers when you only have 1K of Flash? (Hint: it's related to the fact that you only need to be able to do it for numbers up to 999,999, since the counter is only 6 digits long.) (note to self: better figure out whether the program handles rollover at 999,999. It probably doesn't right now, but it would be easy enough to add.)