No video :(

Sieve of Eratosthenes: Background & Python Code

Подписаться 13 тыс.

Просмотров 13 тыс.

50% 1

In this video we'll cover, first the history and basics of the Sieve of Eratosthenes, later we'll open up a coding editor and implement the algorithm using the Python coding language. At the end we compare the computational efficiency against other prime number sieves.
If you'd like to learn about Python data structures, check out my video series starting with: • Python Data Structures...
Video series covering GUI development in Python: • Python GUI Development...
References:
[1] - en.wikipedia.org/wiki/Eratost...
[2] - en.wikipedia.org/wiki/Sieve_o...
[3] - en.wikipedia.org/wiki/Destruc...
In mathematics, the sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit.
It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that 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.
The earliest known reference to the sieve (Ancient Greek: κόσκινον Ἐρατοσθένους, kóskinon Eratosthénous) is in Nicomachus of Gerasa's Introduction to Arithmetic, which describes it and attributes it to Eratosthenes of Cyrene, a Greek mathematician.
One of a number of prime number sieves, it is one of the most efficient ways to find all of the smaller primes. It may be used to find primes in arithmetic progressions.

Опубликовано:

10 авг 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 16

@jonsnow9246 6 лет назад

Another easy way: #soe def soe(n): prime=[True]*(n) multiplier =2 while multiplier

@mikkokylmanen9296 3 года назад

Thank you this is great stuff!

@mdisrafil2491 5 лет назад

Please make video on sieve of atkin

@RacecarsAndRicefish 6 лет назад

This was super helpful for my homework assignment but when I ran numbers like 100,000, it would take around a minute to run... Is there a way to not use nested loops for this?

@BrianFaure1 6 лет назад

Glad it was helpful! I can't really think of any way to achieve this exact Sieve without two nested loops but they're definitely some other prime number Sieves out there that are more efficient. I would look into the Sieve of Atkin because I think it can be implemented in O(n) time complexity. Otherwise, generating prime numbers is well-known to be a relatively difficult task for computers hence the reason why their used so heavily in cryptography. Thanks for the comment!

@judeleon8485 3 года назад

Nice explanation! I stumble on this channel while looking a good tutorial on Segmented Sieve of Eratosthenes. Does any person know a good channel where it was well explained?

@beeilve 5 лет назад

You said both of these algorithms exist in exponential space but it looks to me like the sieve of atkin increases linearly. You increased the input by a factor of 10 and the duration for Atkin increased by a factor of 10. (Almost exactly when you look at it through the lens of orders of magnitude, or if you were to graph this on a logarithmic chart.)

@BrianFaure1 5 лет назад

So after more research, as it turns out I had calculated the time complexity incorrectly, the true time complexity is closer to O(n*log(log(n))), which would explain why the computation time doesn't rise as fast as you would expect from O(2^n). Sorry for the confusion.