The Sieve of Eratosthenes

The first big demo for my homebrew cpu generated prime numbers using a variant of the Sieve of Eratosthenes. Ever since then I’ve had a various comments and requests for more information about the algorithm. This video explains the Sieve and it’s variants with a leaning towards practical implementation, I do cover a few specifics about why I chose this for a first demo but it should serve as a good introduction to the algorithm on it’s own.

This video covers the Sieve, the Segmented Sieve and the Incremental Sieve.

The painting of Eratosthenes I’ve used is “Eratosthenes teaching in Alexandria by Bernardo Strozzi (1635)”

[djc]

Welcome back, I've been missing your videos. I'll have a go at the segmented sieve on my CPU, I've only implemented calculating primes up to 255 at the moment.

[peter.stimpel]

I like such stuff. It recalls good memories of my childhood in the 80s, my first steps with GDR 8bit CPUs. Basic, assembler and pascal. Please, more of it!

[hujkin]

Wonderful video, glad to see you back James!

[Dave]

As usual you've given an excellent description of the task, and an excellent description of how it's done without having to fill the entire address space with one array. A video going over the how-to in assembly would be nice to see, but it would probably be even better if it was a side-by-side video with both assembly and C implementations. (I say this because modern RISC CPU's, especially ARM and MIPS, have instruction sets that were designed to be used with a C/C++ compiler and genuinely are extremely difficult to hand code in assembly with as efficient a result as even the free GCC compiler.) Thanks alot for the video. Always great to watch your videos.

[dualityy]

I really love how you have grown being on camera :)

[yngsjo]

Wonderful description. An example of code in C or something similar would be fun to se.

[LeoBerardino]

Hey James, great video.
Is the CPU finished?

[gregvandenberg]

I would be very interested in seeing a 32 bit implementation of this on your cpu. I assume since you have done this to 16 bits on an 8 bit system, it could be done. Would it be a memory restriction? If so, how about 24 bits?

[zach-]

Hello, I am a teenager interested in all of these types of things. I have a ben eater kit, but I want to build and design an 8bit computer completely from scratch. Where did you learn all of this stuff, books, tutorials, etc. Any recommendations?

[ArtisanASCII]

Are there going to be any more computer videos?

[TheEmbeddedHobbyist]

Can we use the colander of Archimedes as I believe his friend and colleague was also looking in to area of mathematics at the time, but Eratosthenes beat him to it and as we know history never remembers the name of the person who came second. ;-)

[christopherellis]

Rather, . Any number ab is not prime, including a=b, except where a or b equal 1.