# ATtiny2313 prime number generator

[Scott Harden's] prime number generator exhibits a great way to use an LED matrix to present readable information. The project resides in a hinged wooden box with a grid of holes on the lid for the LEDs. [Scott] has overlaid the matrix with a printout showing powers of two that represent different prime numbers. Inside you’ll find an ATtiny2313 microcontroller that handles the column scanning and prime number testing. We’ve embedded a video the break where [Scott] explains the project in great detail, but you should also check out his prototyping and construction pages.

1. ColinB says:

It’s weird that the photo has 2**13 twice but the video has 2**23 in the right spot.

2. ColinB says:

Huh, actually there are other problems with the photo as well! It starts at 2**1, for starters, instead of 2**0.

3. HackerK says:

Kinda useless but I *do* like this project. Very geeky!

Nicely done… ;)

4. HackerK says:

Oh next, is someone up for calculating the value of Pi using a PIC? :)

5. ehrichweiss says:

Fellas…regarding the double 12/13’s…he ran out of 2’s it seems…

6. Scott says:

Yeah, I screwed-up the first print (forgot 2^0 and have a misplaced 2^13) and re-printed it correctly before I shot the video. The code is the same obviously!

7. SparkyGSX says:

The code to find the next prime is horribly inefficient. Ofcourse, the AVR is rather memory-challenged, so a high efficient number sieve probably isn’t possible.

A few suggestions to speed it up:

– calculate the square root of the current number to be tested, instead of squaring the divisor every cycle

– keep track of some prime numbers in the available memory, so the intermediate numbers don’t have to be tested. Keeping the first X primes probably won’t help much, because the frequency of primes if much higher in the small number range, which means you effectively don’t skip many intermediate numbers. Keeping the last X discovered primes won’t do much good either, because most of the time, you won’t get that far before discovering a number isn’t a prime. Deciding which list to keep, if the space is very limited, is a bit of a challenge. Anyway, you could try to take advantage of the fact that any non-prime greater than 2 is dividable by a prime, so it would be best not to try non-primes as divisors, if possible.

8. Scott says:

I’m a dental student, not an engineer or mathematician. Take my projects with a grain of salt and appreciate them for their educational value!

@SparkyGSX There’s no reason to make it run quickly. It’s a novelty, nothing more. I don’t think anyone expects this to rival supercomputers.

At the same time, the most effective algorithm I’ve come across to do this with limited memory is based upon “sieves using binary quadratic forms”, well-documented on http://cr.yp.to/papers/primesieves.pdf and it calculates MILLIONS of prime numbers every second on a standard PC. It’s what I used to calculate the first trillion prime numbers (2^15) on a SheevaPlug plug computer (it took a little less than a year to reach the trillion mark).

Right now it says that the 1,063,620,000,000’th prime number is 31,972,536,554,401. Ironically enough, there’s no way to check it online. The database http://primes.utm.edu/nthprime/index.php stops at 1 trillion, but it was accurate up to that point so I don’t doubt it.

9. amk says:

Neat project Scott. I think we share a passion, finding weird things to do with prime numbers. I’ve spent the last 15 or so years coming up with weird ways to represent prime numbers, or more accurately the distribution of primes, in physical ways. There’s something therapeutic about it.