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!

Comments

  1. emuboy says:

    “Happy birthday, Furball!”

    XD

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

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

  4. Adrian says:

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

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

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

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

  6. jorge says:

    Can you share de code?

    Thanks.

  7. andygoth says:
  8. di0 says:

    wicked neato

  9. Joejoedancer says:

    Wait! Freecad is a functional program?

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

Follow

Get every new post delivered to your Inbox.

Join 91,245 other followers