Числовые функции. Базовые алгоритмы теории чисел. Python
Количество всех натуральных делителей натурального числа n обозначается σ0(n). Сумма всех натуральных делителей числа n обозначается σ1(n).
Входные данные
Дано натуральное n≤10**9.
Выходные данные
Выведите σ0(n) и σ1(n).
Примечание
Данную задачу рекомендуется решать путём перебора всех делителей числа до √n
Примеры
Ввод 6
Вывод 4 12
Подскажите, пожалуйста!!!
Есть подсказка: У каждого делителя d числа n, который меньше √n есть парный ему, равный n/d, больший √n. Будем учитывать их парами. Еще нужно не забыть, что если √n является делителем, то у него нет пары.
Ну что тут подсказывать. Из примера следует, что диапазон значений делителей равен
от 1 до n. При этом кратные делители (например 4*4 или 2*2*2*2 для числа 16) в подсчет входят по одному разу, но зато из них ещё составляются непростые делители,
такие как 2*2*2=8.
Даже имея готовое число в виде произведения заданных сомножителей мы не можем легко решить данную задачу, если встречаются сомножители не простые. Тут наиболее простой способ - перебрать в цикле все натуральные x от 1 до m <= √n .
На Бейсике (VBA в Word или Excel) за секунду сработает от 30 до 150 млн циклов.
Естественно применить функцию поиска if (n Mod x) Then Найдено_ещё_2
и т. п. В случае, если m = √n имеем на 1 делитель меньше, а из суммы надо отнять √n.