На вход подается два натуральных числа a и b (a < b), каждое на новой строке. Напишите программу, которая найдёт число на отрезке [a; b] с максимальной суммой делителей и выведет на экран эту сумму.

Задача (цель: понять решение): На вход подаются два натуральных числа a и b (a < b), каждое на новой строке. Нужно найти на отрезке [a, b] число, у которого максимальна сумма делителей, и вывести эту сумму. Пояснение к идее: - Пусть σ(n) — сумма всех положительных делителей числа n (1 + … + n). - Чтобы получить σ(n) для всех n в диапазоне, можно воспользоваться простой vzt: для каждого возможного делителя d добавляем d ко всем числами, кратным d. - То есть для d = 1..b делаем: для всех m, где m = k*d и m ≤ b, прибавляем σ[m] += d. - В итоге σ[n] будет равно сумме всех его делителей. Затем на диапазоне [a, b] находим максимальное σ(n) и выводим его. Алгоритм: 1. Прочитать a и b. При необходимости поменять местами, если a > b (для надёжности). 2. Создать массив sigma размером b+1, инициализировать нулями. 3. Для d от 1 до b: - для m от d до b шагом d: sigma[m] += d Таким образом σ(n) будет заполнено для всех n ≤ b. 4. Найти max_sigma = max(sigma[a], sigma[a+1], ..., sigma[b]). 5. Вывести max_sigma. Сложность: - Временная: примерно O(b log b) из-за суммирования по кратным. - Память: O(b). Пример кода на Python (работает на обычной школьной задаче): ```python import sys def main(): data = sys.stdin.read().strip().split() if not data: return a = int(data[0]) b = int(data[1]) if a > b: a, b = b, a # небольшая страховка на случай перепута # шаг 2: вычисляем сумму делителей для всех n = 1..b sigma = [0] * (b + 1) for d in range(1, b + 1): for m in range(d, b + 1, d): sigma[m] += d # шаг 4: находим максимум на [a, b] max_sigma = max(sigma[a:b + 1]) # шаг 5: выводим результат print(max_sigma) if __name__ == "__main__": main() ``` Пример теста: - Ввод: 1 10 - Значения σ(n) в диапазоне 1..10: 1, 3, 4, 7, 6, 12, 8, 15, 13, 18 - Максимум на [1,10] равен 18 (при n = 10). Программа выведет 18. Советы по альтернативам: - Если диапазон [a, b] маленький ([b - a] небольшое), можно для каждого n в диапазоне вычислять σ(n) напрямую через разложение на простые делители за O(sqrt(n)) и взять максимум. Это может быть выгодно, если b очень велик, но диапазон узок. - Для очень больших b (например, > 2–5 миллионов) хранение массива sigma может быть тяжёлым на памяти в Python. В таком случае можно реализовать «поэлементный» метод через разложение каждого n в [a, b] и аккуратно суммировать его делители без полного массива, либо использовать язык/среду с более эффективной памятью.