​​💥 Объяснение алгоритма «Решето Эратосфена» за 5 минут

Решето Эратосфена – это алгоритм нахождения всех простых чисел меньше заданного числа.

Алгоритм основан на постепенном отсеивании составных чисел.

Этот метод описан во «Введении в арифметику» Никомаха Герасского (первая половина II в. н. э.). Никомах называет автором метода Эратосфена (конец III – начало II в.в. до н.э.).

Название «решето» метод получил потому, что во времена Эратосфена писали числа на дощечке, покрытой воском, и прокалывали дырочки в тех местах, где были написаны составные числа. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только простые.

Вспомним, что числа являются простыми, если делятся только на единицу и самих себя. Первое простое число - это 2, второе простое число - это 3 и так далее. Теперь начнем рассуждать:

1. Все четные числа, кроме двойки, - составные, т. е. не являются простыми, так как делятся не только на себя и единицу, но еще и на 2.
2. Все числа кратные трем, кроме самой тройки, - составные, так как делятся не только на самих себя и единицу, но и на 3.
3. Число 4 уже выбыло из игры, так как делится на 2.
4. Число 5 простое, так как его не делит ни один простой делитель.
5. Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

Алгоритм Эратосфена заключается в последовательной проверке делимости чисел на предстоящие простые числа.

Алгоритм:

1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
2. Пусть переменная p=2— первому простому числу.
3. Зачеркнуть в списке числа, кратные p (это будут числа: 2p, 3p, 4p, …).
4. Найти первое не зачёркнутое число в списке, большее чем p, и присвоить переменной p это значение.
5. Повторять шаги 3 и 4, пока возможно.

Теперь все не зачёркнутые числа в списке — это простые числа от 2 до n.

Пример для n = 24.

a = 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

1 Шаг. Находим все числа, кратные 2 и удаляем их:

a = 2 3 5 7 9 11 13 15 17 19 21 23

2 Шаг. Находим все числа, кратные 3 и удаляем их:

a = 2 3 5 7 11 13 17 19 23

3 Шаг. Находим все числа, кратные 5 и удаляем их:

Таких чисел нет, поэтому на этом шаге алгоритм останавливается.

Теперь а состоит только из простых чисел, которые меньше 24.

👉🏻 Сложность алгоритма – O(n log(logn))

🧐 Кстати, хотите подробный разбор расчета сложности этого алгоритма?

​​💥 Большая подборка телеграмм-каналов для аналитиков

Мы отобрали для вас более 20 полезных каналов на любой вкус - анализ данных, программирование, data engineering, data science и многое другое 👍

Теперь вам точно будет, что почитать на предстоящих выходных 🙃

​​GROK IT!

❓Задача по Python: Что выведет код?

Правильный ответ раскроем завтра 😏

#grokit

​​💥 Какая Ваша любимая СУБД?

У каждого есть любимый язык программирования, любимая IDE и даже тема для нее.

А что насчет любимой СУБД? Кто Ваш фаворит для работы с Базами данных? 😏

P.S. Наверное, Вы уже догадались, что наша любимая СУБД - PostgreSQL! Только тссс!.., никому 😉

​​GROK IT!

❓Задача по Алгоритмам: Какова сложность вставки элементов в односвязный и двусвязный списки?

Правильный ответ раскроем завтра 😏

#grokit