Если вы ещё не знаете, что такое «Эратосфеново решето», эта статья для вас. Прежде всего вспомним, какие числа называют простыми и составными. Простое число — это натуральное число, не равное 1, которое делится только на 1 и на само себя. Примеры: 2, 3, 5, 7, 11 и т.д. Ну а составное число — натуральное, которое имеет делители, отличные от 1 и самого себя. Примеры: 4, 6, 8, 9 и т.д. С древних времён простые числа привлекали внимание математиков. Древнегреческий математик Евклид, живший за 3 века до н...

Статья подготовлена для студентов курса «Алгоритмы для разработчиков» в образовательном проекте OTUS. Что такое решето Эратосфена, знает сегодня, пожалуй, любой школьник, интересующийся математикой. Но не всякий знает, какова алгоритмическая сложность этого «просеивателя». Напомним условие задачи Необходимо найти все простые числа, меньшие или равные заданному числу N. Запишем в ряд все числа от 1 до N и будем вычёркивать оттуда все числа, кратные двойке, но больше двойки, затем, все числа, кратные тройке, но больше тройки и т...