The Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit. The algorithm does so by iteratively marking as composite the multiples of each prime, starting with the multiples of 2.
According to Wikipedia, the multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them which is equal to that prime. This is the sieve’s key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.
“My little sister is finishing up her graduate degree in mathematics education this year, aiming to teach high school maths and I wanted to give her something besides just a grocery store gift card for her birthday. So I decided to make an Arduino-based demonstration of the Sieve of Eratosthenes, the prime number derivation sieve, that she can set on her desk and show her students,” Darkmoonsinger explained in a blog post about the project.
“First I bought myself an LED matrix and an 8-digit LED display driver (MAX7219) and soldered that all together and popped the LED matrix on. I hooked it up to my Arduino and ran some simple test code to make it run numbers (the original intention for the driver). Figured out how to address each LED individually. Then [I] got my Arduino Nano involved and got it breadboarded, wrote up the algorithm and got that going. [I then] soldered the whole thing to some stripboard, which meant I was in business.”
With the hardware side of things complete, Darkmoonsinger designed and 3D printed a slick enclosure for the Arduino-powered Sieve of Eratosthenes. Pretty cool, eh? No doubt Greek mathematician Eratosthenes of Cyrene would agree!
Interested in learning more? Be sure to check out Darkmoonsinger’s official Eratosthenes project page here.