Embeded Sieve of Eratosthenes: Hunting Primes on ARM

Embeded Sieve of Eratosthenes

I ended up with just enough time over the weekend to pull together a quick project. I implemented the Sieve-of-Eratosthenes on an ARM chip.

If you haven’t heard of the Sieve of Eratosthenes then you really need to work your way through Project Euler. That’s where I first learned about this method of finding prime numbers. You begin with a list of all numbers, find a prime, then remove all multiples of that prime from the list. The real trick with doing it on a microcontroller is to figure out how to store a large list of numbers in a limited space. The gist of my method was to use a boolean array (I call it a bit-packed array but that may be the wrong way of saying it). The details are found in my project linked at the top.

‘Why?’ is almost always the wrong question to ask around here. But in this case, I did this because I wanted to try out the Bit Banding functionality of the ARM core. These chips have alias addresses that map to a single bit in the SRAM and also some of the peripheral registers. This allows read or write access for a single bit using a single instruction. Turns out that one side effect of 32-bit architecture is having addresses to burn.