Раньше это была одна из популярных задачек для тестового. А как обстоят дела сейчас? Делитесь в комментариях, если встречали недавно :-)
Условие задачи
Напишите функцию, которая подсчитывает количество простых чисел в промежутке от 2 до N. Число N задается произвольно в виде аргумента функции. Чем больше N, для которого функция может вывести результат за минуту, тем лучше.
Пример ввода: 20
Пример вывода: 8
Решение
Вспомним, что натуральное число называется простым, если оно делится без остатка только на два числа: единицу и само себя.
Конечно, можно заняться банальным перебором: пройти от 2 до N и для каждого числа проверить делимость на числа от 2 до самого себя. Но это не профессионально.
Поэтому применим решето Эратосфена:
🔵 Инициализация. Создаем массив логических значений, где индекс будет представлять число, а значение будет указывать, является ли число простым (true) или составным (false). Пусть массив будет размером *N+1*, так как мы считаем числа от 2 до N.
🔵 Итерация. Начнём с 2 и будем работать с каждым числом до N. Если текущее число не вычеркнуто, то оно простое, и мы можем вычеркнуть все его кратные.
🔵 Подсчёт простых чисел. В конце мы просто посчитаем числа, которые остались невычеркнутыми.
Также можно описать решение функцией на Python, попробуете написать код в комментариях?
#разбор_тестового
🔜 @leftjoin_career