Arduino-based Sieve of Eratosthenes

ofTs7UD

[Darkmoonsinger’s] sister is finishing her graduate degree in mathematics, and [Darkmoonsinger] wanted to give her a gift that fit with her achievement. Naturally, building a Sieve of Eratosthenes using an LED matrix and an Arduino made perfect sense. If you’re unfamiliar, a Sieve of Eratosthenes is a simple, but very efficient, technique for finding prime numbers. Starting with a group of numbers, you step through each one in order. If it’s prime, you eliminate any multiples from the list. After a few iterations, the numbers remaining are all primes. After getting the LED matrix and sieve algorithm running, [Darkmoonsinger] designed an enclosure for the project. She made a couple of mistakes with this part, and happily included them for everyone’s benefit.

It only figures primes up to 64, and she lights the LED for 1 because it ‘makes the array look prettier’. Also, we couldn’t help but think that mounting the components a bit differently would have made a cleaner install (here’s a prime number generator with a backlit faceplate). However, that probably doesn’t matter to his sister. As they say, it’s the thought that counts, and we never get tired of seeing people build rather than buy!

25 thoughts on “Arduino-based Sieve of Eratosthenes

  1. It seems like that case was complete overkill, so much unused space! It is the thought that counts but I hope he realised how more compact it could have been and not used up nearly as much 3D printer plastic!!

  2. I’m a she, and yes, I realised how much more compact it could have been, but I wanted to show everything that went into it AND leave the USB in so my sister could reprogram it if she wanted.

    1. How is it close to the least efficient algorithm? It runs in O(n log log n) time, which is much, much better than the naive algorithm (go through all the numbers up to some max, see if each number n in that range divides by any number up to the square root of n), which runs in O(n^3/2) time. Not even close to least efficient.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s