Задание 25 это задание на составление программы и нахождение с ее момощью ответа. В задании нет входных файлов, как и в задании 17, тут есть диапазон чисел, среди которых необходимо дать ответ на вопрос.
Два стандартных алгоритма, которые необходимо знать для решения данного задания:
- Поиск делителей числа
- Определение, является ли число простым.
И тот, и другой алгоритм имеет несколько реализаций, в зависимости от степени оптимизации.
Поиск делителей числа
Простейший алгоритм для нахождения всех делителей числа – это просто перебрать все числа от 1 до данного числа и проверять каждое из них на остаток от деления.
В приведенной ниже программе все делители числа складываются в список dividers
Зачастую в данной задаче исключается единица и само число. В этом случае следует изменить границы цикла на range(2, n).
Данный алгоритм можно ускорить. Очевидно, что число не может делиться ни на одно число, которое больше его половины. Если мы ищем делители 100, то после 50 пойдут числа, которые превышают половину от 100, и делить на них смысла нет.
Можно пойти еще дальше в ускорении алгоритма. Делители числа парны.
Для 100:
100 = 1 * 100
100 = 2 * 50
100 = 4 * 25
100 = 5 * 20
100 = 10 * 10
100 = 20 * 5
100 = 25 * 4
100 = 50 * 2
100 = 100 * 1
После стрки, отмеченной полужирным шрифтом, делители теже самые, только в паре они стоят наоборот. Таким образом, находя один делитель, мы можем получить парный для него, если поделим число на найденный делитель. В таком случае можно сделать перебор чисел только до корня из числа. Также можно заметить что в паре 10*10 мы видим один и тотже делитель. Особенность этой строки заключается в том, что она есть только у чисел, которые являются квадратом числа, т.е. из которых можно взять корень. Чтобы исключить добавление дважды такого делителя в питоне мы можем взять не списко, а множество, элементы которого уникальны. Добавлять будем найденные делители и парные им.
Для удобства алгоритм можно оформить в виде функции
Функция принимает на вход число, а возвращает множество делителей этого числа, начиная с 2 и не включая само число. Следует учитывать, что множества в питоне это объект изменяемый, как и списки.
Является ли число простым
Данный алгоритм основывается на предыдушем. Идея проста. Если число простое, у него нет делителей кроме 1 и его самого. Значит, при поиске делителей мы их не найдем. А если найдется хотябы один делитель, значит, число составное.
Сразу оформим код в виде функции
Функция принимает на вход число, а возвращает True или False если число простое или составное соответственно.
Приведенные алгоритмы помогут решить 25 задание. Это не единственные реализации этих алгоритмов, но в контексте 25 задания это самый простой и удобный способ решить задачу.