Calculating Prime Numbers with the Sieve of Eratosthenes

This video builds on the previous program where we calculated primes in a very naive way. Here we look at the Sieve of Eratosthenes! The theory is briefly covered and then the C program is adapted to use this method. Running the program at the end shows how much faster it is!

00:00 Introduction
00:22 The sieve of Eratosthenes
01:14 The theory
04:25 Adapting the code to use the sieve
08:48 Adapting the Makefile and first run
09:55 Optimizing the sieve by marking from the square
14:25 Second run with the optimization

#primenumber
#sieve
#eratosthenes

[robharwood]

One fun mathematical project is to use the Sieve of Eratosthenes -- instead of storing merely 1 or 0 whether prime or not -- to store the smallest prime factor of the number. This essentially gives you a cache that allows you to quickly find the unique prime factorization of any number below your maximum. For example, if your maximum is 2^16-1 (equals 65535), then you can have a table which only takes up 64k bytes (since maximum prime factor is less than 255, i.e only need one byte of storage per number), and which allows you to quickly find the unique prime factorization of any number from 0 to 65535. Just iteratively look up the number in the table to find the first smallest prime, then divide your number by that small prime to get the next factor to decode, and so on.

[robharwood]

In English it's pronounced: air a TOSS the knees.
In Greek it sounds much more like: era toas' THE' niece. (Where toas' is like toast, but without the last t, and THE' is like THERE, but without the RE.)
I like the flow of the Greek better, as the beginning is easily remembered as being similar to the word 'errata', and the end sounds more authentically Greek like Heracles rather than the romanized Hercules.