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. FYI, Darkmoonsinger is a she, not a he. Could you fix the pronouns in your article? Thanks!

1. Yarr says:

Still says “However, that probably doesn’t matter to his sister.”

1. Geebles says:

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!!

1. Waterbury says:

The excess plastic could have been used to fill in the cracks of a leaking dam.

2. Darkmoonsinger says:

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. lol says:

Leave a hole so the USB cable could be connected from the outside?…

1. Theodore Wahrburg says:

Then there would have been a USB cable sticking out of the top.

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

2. Blue Footed Booby says:

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

Very efficient? Its close to the least possibly efficient algorithm. What about it is efficient?

1. Trui says:

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. vpoko says:

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.

1. vpoko says:

Err, that should read O(n^(3/2)), not O(n^3/2)

4. vpoko says:

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

1. cheeseslices says:

You sir have just won at life.

1. vpoko says:

At the risk of losing my award, I should say that I stole that from the Wikipedia article.

1. Mike says:

And a gracious winner.

5. jorge says:

Can you share de code?

Thanks.

6. di0 says:

wicked neato

7. Joejoedancer says:

Wait! Freecad is a functional program?

1. I found it to be, but it was my first serious CAD program usage. It was recommended by a friend when I first started CADding things a couple months ago.

Please be kind and respectful to help make the comments section excellent. (Comment Policy)

This site uses Akismet to reduce spam. Learn how your comment data is processed.