Найти сумму всех делителей заданного натурального числа

Найти сумму всех делителей заданного натурального числа

Условие задачи 2.16

Задача 2.16
Дано натуральное число N. Вывести на экран сумму его делителей. Число 1 считается делителем любого натурального числа. Число N не является делителем числа N.

Эту задачу довольно часто задают в контрольных и прочих студенческих делах. Задача несложная. Однако на её примере начинающие могут кое-чему научиться.

Алгоритм решения довольно простой:

  1. Перебираем в цикле все возможные целые числа от 1 до числа N.
  2. Каждый раз пытаемся делить число N на текущее число. Если оно делится без остатка, то текущее число является делителем числа N. Прибавляем его к итоговой сумме.

Разумеется, сначала подготавливаем необходимые переменные.

Ну а чтобы задачка была поинтереснее, предлагаю дополнительно сделать так, чтобы на экран была выведена не только итоговая сумма делителей числа N, но и сами делители.

Решения на Паскале и С++ представлены ниже. Если кто забыл, что такое натуральное число, то см. здесь.

Краткое описание программы:

  1. Обнуляем переменную Sum, в которой у нас будет итоговая сумма делителей.
  2. Получаем случайное значение и записываем его в переменную N.
  3. Затем запускаем цикл от 1 до N и в каждой итерации цикла вызываем нашу функцию ThisDivider(N, i), которая возвращает TRUE, если число i является делителем числа N. Саму функцию описывать не буду, потому что она достаточно простая.
  4. Если число i является делителем числа N, то к переменной Sum мы прибавляем число i, а к строке Str присоединяем строковое представление числа i, предварительно преобразовав это число в строку. Так мы получаем строку, которая содержит все делители числа N.
  5. Ну и в конце выводим всё на экран.

Обратите внимание, что для использования функции преобразования числа в строку в Паскале надо подключить модуль SysUtils, а в С++ — .

Читайте также:  Как подключить йоту к телефону андроид

Также обратите внимание на то, как мы преобразуем число в строку на С++. Делается это довольно замысловато. И это ещё не самый сложный способ. В Паскале же всё просто и интуитивно понятно. Ну а в С++, как всегда, всё через зад.

Правда, начиная со стандарта С++ 2011 года (вроде с него), появилась более понятная и приятная функция to_string(). Но плохая новость заключается в том, что далеко не все средства разработки (особенно бесплатные) поддерживают этот стандарт. Поэтому я не стал использовать эту функцию в своей программе.

Учитывая натуральное число n , задача состоит в том, чтобы найти сумму делителей всех делителей числа n.

Примеры:

Используя тот факт, что любое число n можно выразить как произведение простых факторов, n = p 1 k1 xp 2 k2 x… где p 1 , p 2 ,… — простые числа.
Все делители n могут быть выражены как p 1 a xp 2 b x…, где 0 0 , p 1 1 , …., p 1 k1, умноженных на всю степень p 2 — p 2 0 , p 2 1 ,…., P 2 k1
Сумма делителей n
= (p 1 0 xp 2 0 ) + (p 1 1 xp 2 0 ) +… .. + (p 1 k1 xp 2 0 ) +…. + (p 1 0 xp 2 1 ) + (p 1 1 xp 2 1 ) +… .. + (p 1 k1 xp 2 1 ) + …… .. +
(p 1 0 xp 2 k2 ) + (p 1 1 xp 2 k2 ) + …… + (p 1 k1 xp 2 k2 ).
= (p 1 0 + p 1 1 +… + p 1 k1 ) xp 2 0 + (p 1 0 + p 1 1 +… + p 1 k1 ) xp 2 1 + ……. + (p 1 0 + p 1 1 +… + p 1 k1 ) xp 2 k2 .
= (p 1 0 + p 1 1 +… + p 1 k1 ) x (p 2 0 + p 2 1 +… + p 2 k2 ).

Теперь делителями любого p a при p в качестве простого числа являются p 0 , p 1 , ……, p a . И сумма делителей будет (p (a + 1) — 1) / (p -1), пусть это определится как f (p).
Таким образом, сумма делителей всех делителей будет,
= (f (p 1 0 ) + f (p 1 1 ) +… + f (p 1 k1 )) x (f (p 2 0 ) + f (p 2 1 ) +… + f (p 2 k2 )) ,

Итак, для заданного числа n путем простой факторизации мы можем найти сумму делителей всех делителей. Но в этой задаче нам дано, что n является произведением элемента массива. Итак, найдите простую факторизацию каждого элемента и, используя факт a b xa c = a b + c .

Читайте также:  Фотошоу pro как сохранить видео

Ниже приведена реализация этого подхода:

// C ++ программа для поиска суммы делителей всех
// делители натурального числа.
#include

using namespace std;

// Возвращает сумму делителей всех делителей
// из n

Все делители числа

Все делители, на которые данное число делится нацело можно получить из разложения числа на простые множители.

Нахождение всех делителей числа выполняется следующим образом:

  1. Сначала нужно разложить данное число на простые множители.
  2. Выписываем каждый полученный простой множитель (без повторов, если какой-то множитель повторяется).
  3. Далее, находим всевозможные произведения всех полученных простых множителей между собой и добавляем их к выписанным простым множителям.
  4. В конце добавляем в качестве делителя единицу.

Например, найдём все делители числа 40. Раскладываем число 40 на простые множители:

Выписываем (без повторов) каждый полученный простой множитель – это 2 и 5.

Далее находим всевозможные произведения всех полученных простых множителей между собой:

2 · 2 = 4
2 · 2 · 2 = 8
2 · 5 = 10
2 · 2 · 5 = 20
2 · 2 · 2 · 5 = 40

Добавляем в качестве делителя 1. В итоге получаем все делители, на которые число 40 делится без остатка:

1, 2, 4, 5, 8, 10, 20, 40

Других делителей у числа 40 нет.

Калькулятор нахождения всех делителей

Данный калькулятор поможет вам получить все делители числа. Просто введите число и нажмите кнопку "Вычислить".

Ссылка на основную публикацию
На клавиатуре клавиши или кнопки
С появлением первых компьютеров, клавиатура меняла свой вид и функционал. Добавились и новые клавиши которые пользователям не известны, не говоря...
Можно ли подрезать защитное стекло для смартфона
«MyTooling.ru» – информационный портал, предоставляющий полную информацию о всех инструментах от А до Я, с которым действительно приятно работать! Наверное,...
Можно ли подключить графический планшет к телефону
Сомневаетесь в ваших новых планшетах Huion HS610 и HS64? Не волнуйтесь, в этой статье вы найдете часто задаваемые вопросы об...
На кого зарегистрирован номер телефона узнать бесплатно
«Проверка сотового номера» - это уникальный онлайн сервис для проверки номеров. База данных сервиса насчитывает более 600 млн данных о...
Adblock detector