Arduino-based Sieve of Eratosthenes


[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. Theodore/Ted has the idea- I didn’t want to just leave a hole in it , so I used the USB for power as well and left it plugged in. The hole for the USB cable I put in the back, down low (stability) and filled in for strain relief.

    1. The English language would be a lot better off with a specifically singular genderless pronoun that doesn’t imply non-personhood.

    1. It’s an efficient algorithm if you want to find all primes < some number that's not too large.

      It's a bad algorithm if you only need one, or if you need big primes.

    2. 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.

  3. Sift the Two’s and Sift the Three’s,
    The Sieve of Eratosthenes.
    When the multiples sublime,
    The numbers that remain are Prime.

Leave a Reply

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

You are commenting using your 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