Sieve of Eratosthenes
Channel: dionyziz
Date: 2016-08-16

The Sieve of Eratosthenes: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Trial division: https://en.wikipedia.org/wiki/Trial_division

For an introduction to complexity and big-O, big-Ω notation see: https://dionyziz.com/complexity/

Soup's number theory book: http://www.shoup.net/ntb/ntb-v2.pdf

This is a classical number theory algorithm implementation in Python. 

The Sieve of Eratosthenes and trial division are the simplest way of determining whether a number is a prime, a primality test. This is an exponential way of checking for primality, as the complexity is Ω(sqrt(n)).

Primality testing has many applications including cryptography.

If you liked this video, please thumbs up and subscribe. This is one of my first videos. Please leave feedback about what you think I can improve and what other topics you would like to see.

I've just created a Patreon where you can buy me a cup of coffee. Thanks so much for supporting me! https://www.patreon.com/dionyziz