Решето Эратосфена – алгоритм определения простых чисел. Решение задачи на Python
Решето Эратосфена – это алгоритм, оставляющий в ряду натуральных чисел только простые числа.
Первым простым числом считается двойка.
Здесь зачеркнуты составные числа. А 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. Все это уменьшит количество проходов по циклам.
Это прокомментированный пример без оптимизации алгоритма. Здесь список заполняется обычным способом, а не с помощью выражения-генератора списка.
От нулей избавляемся через превращение списка во множество. Во множестве как известно не бывает одинаковых значений. Остается один ноль, его удаляем. И превращаем множество обратно в список.
Текстовое описание решения задачи и исходный код программы: https://younglinux.info/algorithm/sieve
Больше задач: https://younglinux.info/python/task
Приложение для андроид: https://play.google.com/store/apps/de...
Купить PDF-версию (100 задач): https://younglinux.info/store/store.h...
Смотрите видео Решето Эратосфена – алгоритм определения простых чисел. Решение задачи на Python онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь Лаборатория линуксоида 19 Декабрь 2021, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 21,11 раз и оно понравилось 25 людям.