C++ СИРИУС Числовые функции
Количество всех натуральных делителей натурального числа n обозначается σ0(n). Сумма всех натуральных делителей числа n обозначается σ1(n).
Входные данные
Дано натуральное n≤10^9.
Выходные данные
Выведите σ0(n) и σ1(n).
Примечание
Данную задачу рекомендуется решать путём перебора всех делителей числа до √n.
Примеры
Ввод
6
Вывод
4 12
Answers & Comments
Ответ:
int main()
{
unsigned int value = 0;
std::cout << "input value <= 10^9: ";
std::cin >> value;
if (value > 1000000000)
{
std::cout << "incorrect value";
_getch();
return 0;
}
unsigned int i = 1;
unsigned int count = 0;
unsigned int sum = 0;
while (true)
{
if ((value % i) == 0)
{
unsigned int res = value / i;
if (res < i)
break;
count += 1;
sum += i;
if (res == i)
break;
count += 1;
sum += res;
}
i++;
}
// выводим
printf("%u %u", count, sum);
_getch(); // экран не закрывается, пока не нажата клавиша
return 0;
}
Объяснение:
После запроса значения оно проверяется на максимальное значение.
i - счетчик цикла и одновременно очередной делитель, на который и проверяется возможность деления нацело заданного значения.
Если результат деления оказался меньше делителя, это означает, что мы перешагнули рубеж в √n и надо прекратить цикл.
Иначе количество делителей увеличивается на 1 и к сумме прибавляется этот делитель.
Если результат деления равен делителю, то на этом заканчиваем цикл. Например при вводе 36 последним делителем будет 6 и мы его считаем 1 раз.
В противном же случае, результат деления - это тоже делитель, поэтому еще раз увеличиваем счетчик количества и увеличиваем на него сумму.
#SPJ1