«Просеиваем двойку и просеиваем тройку,
Решето Эратосфена.
Когда кратные великие,
Оставшиеся числа - простые». - Анонимный

Одна из вещей в моем мысленном списке дел - постоянно практиковаться в решении задач кодирования и совершенствоваться в этом. Я столкнулся с этой проблемой, которая гласит что-то вроде «Список всех простых чисел от 1 до N», и мне пришлось закодировать решение для ее решения.

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

Идея

Идея в том, что у нас есть список натуральных чисел от 2 до N, и мы прорабатываем его с помощью нашего алгоритма.

  1. Начните с 2 и избавьтесь от всех чисел, кратных 2.
  2. Перейдите к следующему числу и повторите процесс удаления кратных этого числа. (например, если это 3, избавьтесь от всех кратных 3–3 * 2, 3 * 3…)
  3. Как только вы закончите с этим, избавляясь от каждого значения и его кратных, у вас останутся только простые числа.

Это работает как по волшебству. Если мы перейдем к нашему основному определению простого числа, это число, которое имеет только два фактора (1 и само число). В сите эратосфенов, начиная с 2, мы избавляемся от каждого числа с его кратными, что в основном оставляет нам только простые числа.

Преобразование теории в код

Хотя я понимал алгоритм, у меня было несколько проблем, пытаясь заставить код работать. Моя основная проблема заключалась в попытке выяснить условие остановки в цикле for. Снова немного погуглил, и я смог понять это.

Это базовый рабочий процесс моего кода:

  1. Инициализируйте массив размера N + 1 со всеми нулями.
  2. Запустить цикл for: for: 2 → sqrt (N)
  3. Имитируйте действие исключения как присвоение 1 массиву по соответствующему индексу.
  4. Теперь для каждого числа нам нужно исключить его кратные.
  5. Вот и все. Вывести все индексы массива, значение которого равно 0. (без пометки)

Это мой код:

Как видите, в моем внутреннем цикле я немного боролся с поиском способов проверки условия остановки. Код можно сделать намного лучше, но это основная идея реализации сита из эратосфена.

Если вы реализовали это раньше, или у вас есть отзывы для меня? Как мне улучшить свою интуицию при решении подобных задач, не стесняйтесь сообщать мне в комментариях.

Любые отзывы приветствуются!

Спасибо за чтение!

Подробнее откуда это взялось

Эта история публикуется в журнале Noteworthy, куда каждый день приходят тысячи людей, чтобы узнать о людях и идеях, формирующих наши любимые продукты.

Следите за нашей публикацией, чтобы увидеть больше историй о продуктах и ​​дизайне, представленных командой Журнала.