Лаборатория линуксоида Решето Эратосфена алгоритм определения простых чисел. Решение задачи на Python

🎯 Загружено автоматически через бота: 🚫 Оригинал видео: 📺 Данное видео принадлежит каналу «Лаборатория линуксоида» (@younglinux). Оно представлено в нашем сообществе исключительно в информационных, научных, образовательных или культурных целях. Наше сообщество не утверждает никаких прав на данное видео. Пожалуйста, поддержите автора, посетив его оригинальный канал. ✉️ Если у вас есть претензии к авторским правам на данное видео, пожалуйста, свяжитесь с нами по почте support@, и мы немедленно удалим его. 📃 Оригинальное описание: Решето Эратосфена – это алгоритм, оставляющий в ряду натуральных чисел только простые числа. Первым простым числом считается двойка. Здесь зачеркнуты составные числа. А 2, 3, 5, 7, 11, 13, 17 являются простыми, их нельзя разделить ни на какое предшествующее им другое простое число. Если же число составное, то оно раскладывается на простые множители, то есть должно делиться на что-то впереди стоящее. Алгоритм решета Эратосфена заключается в том, что сначала ряд натуральных чисел просматривается на наличие в нем всех чисел, кратных двум. Потому что если число больше двух и делится на 2, значит оно составное. Все четные, кроме двойки, вычеркиваются из ряда. Следующее число – это 3. Оно априори простое, потому что иначе делилось бы на какое-нибудь число, стоящее до него, и было бы уже вычеркнуто. Теперь из ряда удаляются все числа, кратные трем, то есть каждое третье, начиная с тройки. Понятно, что какие-то из чисел были удалены ранее, на этапе проверки кратности к двойке. Но это не страшно. Следующее за тройкой натуральное число – это 4. Его уже нет, так как оно было кратно двойке. Это составное число. Следующее число – пятерка. Она не затерта, следовательно это простое число. Вычеркиваем из ряда все числа, кратные пятерке. И так далее. Теперь напишем программу на Python. В переменной n будет храниться последнее натуральное число ряда. Создадим список целых чисел до n включительно. У нас индексы ячеек будут совпадать с их значениями. Например, в ячейке с индексом 2, находится число 2. Так алгоритм и программа будут проще. Будем из ряда убирать все непростые числа, заменяя их нулями. Число 1 нам не нужно, поэтому сразу записываем в ячейку 0. Цикл начнется с двойки. Пока i меньше n. На самом деле здесь можно как минимум разделить на 2, потому что когда i равна половине ряда, то i i будет равно последнему элементу ряда. То есть перебирать числа после прохождения половины смысла нет. А еще на самом деле тут можно извлечь корень из n. Если текущая ячейка не забита нулем, значит мы встретили очередное простое число. Будем вычеркивать кратные ему числа. Первое кратное будет в 2 раза больше, чем i. Поскольку надо будет добавлять i множество раз, понадобится цикл. Пока j меньше или равно n, в ячейку j записываем 0. И увеличиваем j на величину i. Не забываем в конце внешнего while перейти к следующему натуральному числу. Посмотрим, что получилось. Вместо составных чисел стоят нули. Чтобы избавиться от них, можем создать другой список. Данный алгоритм можно улучшить. Есть определенные математические закономерности. И здесь можно не удваивать i, а сразу возводить в квадрат. Здесь, как уже было сказано, можно извлечь квадратный корень из n. Это то же самое, что возвести в степень 0.5. Все это уменьшит количество проходов по циклам. Это прокомментированный пример без оптимизации алгоритма. Здесь список заполняется обычным способом, а не с помощью выражения-генератора списка. От нулей избавляемся через превращение списка во множество. Во множестве как известно не бывает одинаковых значений. Остается один ноль, его удаляем. И превращаем множество обратно в список. Текстовое описание решения задачи и исходный код программы: Больше задач: Приложение для андроид: Купить PDF-версию (100 задач): #!digiseller/detail/2882070